題意：給出n個工作，已知每個工作需要的時間last,以及截止時間end,（必須在截止時間之前完成）問最多能夠完成多少個工作

?

首先預處理，將這n件任務按照截止時間從小到大排序

然后用一個cur記錄當前做任務花費的時間， 如果發現當前cur>a[i].end,那么就將隊列里面目前最大的last刪除，把這個a[i].last加入隊列

可以這樣想，把更小的放進去，那么可以為后面的任務騰出更多的時間

然后每刪除一次隊列里面的元素（即不做這個任務），ans++, 最后能夠完成的任務就是n-ans

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 #define mod=1e9+7; 12 using namespace std; 13 14 typedef long long LL; 15 const int maxn=800005; 16 17 struct node{ 18 int last,end; 19 } a[maxn]; 20 21 int cmp(node n1,node n2){ 22 return n1.end<n2.end; 23 } 24 25 int main(){ 26 int t,n,i,j,cur,ans; 27 scanf("%d",&t); 28 while(t--){ 29 scanf("%d",&n); 30 for(i=0;i<n;i++) scanf("%d %d",&a[i].last,&a[i].end); 31 sort(a,a+n,cmp); 32 priority_queue<int> pq; 33 34 cur=0; 35 ans=0; 36 for(i=0;i<n;i++){ 37 cur+=a[i].last; 38 pq.push(a[i].last); 39 if(cur>a[i].end){ 40 cur-=pq.top(); 41 pq.pop(); 42 ans++; 43 } 44 } 45 printf("%d\n",n-ans); 46 if(t) printf("\n"); 47 } 48 return 0; 49 } View Code

?

?

?

話說還是看的題解= = 因為自己想成了今年暑假不AC那樣的，求最大數量的不相交的題目 是這樣轉化的，用每一個end-last作為區間的左端點，end作為右端點來做 這樣就轉化成了求n個區間里面不相交的區間數量

可是 為什么它非得在end-last那一天開始做那件任務呢= =

只需要在截止的時間之前把任務做了就行啦，不一定非得恰好到截止時間才來做 所以這樣想就不對啦= =

?

go---go---go--

?

轉載于:https://www.cnblogs.com/wuyuewoniu/p/4370345.html

總結

以上是生活随笔為你收集整理的UVa 1153 Keep the Customer Satisfied 【贪心 优先队列】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。