洛谷P2751[USACO]工序安排

时间：2023-01-15 10:09:44

　　题目传送门

　　怎么说呢，这个题目我刚开始随便乱搞了几下，交了个暴力代码上去居然还水了49分，数据确实有点弱啊，然后看到洛谷上那位大佬Redbag的题解瞬间就佩服的五体投地，那真的是简洁、易懂又高效。直接用一个结构体和一个优先队列，两边贪心扫过去就水过了。。。。。。Orz。我想我不需要多说，看代码就可以懂了：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

int n,numa,numb;

int ans,t[];

struct Node{

  int s,v;//v表示该机器的效率，s表示用该机器完成工作的总时间;

  bool operator< (Node zo)const

  {return s>zo.s;}

}x;

priority_queue<Node>team;//优先队列

int main()

{

  std::ios::sync_with_stdio(false);

  cin>>n>>numa>>numb;

  for(int i=;i<=numa;i++){

    cin>>x.v;

    x.s=x.v;

    team.push(x);//入队

  }

  for(int i=;i<=n;i++){

    x=team.top();

    team.pop();

    t[i]=x.s;//从第一个工作开始贪心;

    x.s+=x.v;//贪心完后在将总时间加上效率，再次入队

    team.push(x);

  }

  while(!team.empty())team.pop();
//做完以后清空队列;

  for(int i=;i<=numb;i++){

    cin>>x.v;

    x.s=x.v;

    team.push(x);//入队

  }

  for(int i=n;i>=;i--){

    x=team.top();

    team.pop();

    if(t[i]+x.s>ans)ans=t[i]+x.s;
//从后往前贪心，如果该件机器完成工作的时间大于答案
//就更新答案的值，这里不用考虑前面，从后往前贪心对
//前面的状态没有影响

    x.s+=x.v;

    team.push(x);//如上，再次入队

  }

  cout<<t[n]<<" "<<ans;

  return ;

}
//大佬的思路是不是极其巧妙、简洁？

果然大佬就是大佬，我这个蒟蒻要学的还很多啊

相关文章