【uva 1153】Keep the Customer Satisfied（算法效率-贪心+优先队列）

【uva 1153】Keep the Customer Satisfied（算法效率–贪心+优先队列）

全栈程序员-站长 • 2022年2月22日下午2:00 • 未分类 • 阅读 45

大家好，又见面了，我是全栈君。

题意：有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 }