UVa 1153 Keep the Customer Satisfied 【贪心优先队列】

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：给出n个工作，已知每个工作需要的时间last,以及截止时间end,（必须在截止时间之前完成）问最多能够完成多少个工作

首先预处理，将这n件任务按照截止时间从小到大排序

然后用一个cur记录当前做任务花费的时间，如果发现当前cur>a[i].end,那么就将队列里面目前最大的last删除，把这个a[i].last加入队列

可以这样想，把更小的放进去，那么可以为后面的任务腾出更多的时间

然后每删除一次队列里面的元素（即不做这个任务），ans++, 最后能够完成的任务就是n-ans

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 #define mod=1e9+7;

 using namespace std;

 typedef long long LL;

 const int maxn=;

 struct node{

     int last,end;

 } a[maxn];

 int cmp(node n1,node n2){

     return n1.end<n2.end;

 }

 int main(){

     int t,n,i,j,cur,ans;

     scanf("%d",&t);

     while(t--){

         scanf("%d",&n);

         for(i=;i<n;i++) scanf("%d %d",&a[i].last,&a[i].end);

         sort(a,a+n,cmp);

         priority_queue<int> pq;

         cur=;

         ans=;

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

             cur+=a[i].last;

             pq.push(a[i].last);

             if(cur>a[i].end){

                 cur-=pq.top();

                 pq.pop();

                 ans++;

             }

         }

         printf("%d\n",n-ans);

         if(t) printf("\n");

     }

     return ;

 }