大家好，又见面了，我是全栈君。
题意：有N个工作，已知每个工作需要的时间和截止时间。要求所有工作穿行完成，第一项任务开始的时间不早于时刻0。问最多能完成多少个工作。(N≤800000)
解法：贪心。可以模型化题目为：已知N个任务的长度和右端点的限制位置，问最多能完成的任务的个数。——也就是每一步在一定条件下要使得数目尽量大，以及时间尽量短（最优）。
于是可以按截止时间（这就是条件●_●）从小到大排序，先考虑截止时间早的，暂时放入选择的队列中，加入其时间。接着对于当前新的工作，若按当前选择的工作的情况无法在截止时间之前完成这个工作，分2种情况讨论：（1）当前工作需要的时间比选择的队列中工作时间最长的还要长，就放弃这个工作，使完成相同数目工作的耗时尽量小；（2）工作时间比队列中时间最长的要短，就删去队列中时间最长的任务并且将当前的工作加入队列。–“最优子结构” 这样O(n)扫一次，加上使用优先队列，时间复杂度就是O(n log n)。
P.S.不能不判断就选了第一个……
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<algorithm> 5 #include<iostream> 6 #include<queue> 7 #include<vector> 8 using namespace std; 9 10 const int N=(int)8e5+10; 11 int n; 12 struct node{ int d,t;}a[N]; 13 priority_queue<int> q; 14 15 bool cmp(node x,node y) { return x.t<y.t;} 16 int main() 17 { 18 int T; 19 scanf("%d",&T); 20 while (T--) 21 { 22 scanf("%d",&n); 23 for (int i=1;i<=n;i++) 24 scanf("%d%d",&a[i].d,&a[i].t); 25 sort(a+1,a+1+n,cmp); 26 while (!q.empty()) q.pop(); 27 int sum=0,cnt=0; 28 for (int i=1;i<=n;i++) 29 { 30 if (sum+a[i].d<=a[i].t) 31 { 32 q.push(a[i].d); 33 sum+=a[i].d, cnt++; 34 } 35 else 36 { 37 if (q.empty()) continue;// 38 int x=q.top(); 39 if (a[i].d<x) 40 { 41 sum=sum-x+a[i].d; 42 q.pop(),q.push(a[i].d); 43 } 44 } 45 } 46 printf("%d\n",cnt); 47 if (T) printf("\n"); 48 } 49 return 0; 50 }
转载于:https://www.cnblogs.com/konjak/p/6055552.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/108787.html原文链接：https://javaforall.net
