Task

?

比賽當時思路想的差不多，感覺能過的，該處理的也都處理到了，最后還是沒過，可能是二分寫錯了吧-。-

大意：給你n個機器，m個要完成的任務(wù)，每個機器跟任務(wù)都有兩個屬性，機器是最大工作時間跟等級，任務(wù)是需要工作的時間跟等級。完成一個任務(wù)可以得到500*（工作時間）+2*（等級）的報酬。完成任務(wù)的條件是機器的工作時間滿足任務(wù)的需要，等級要大于等于任務(wù)的等級，一個機器只能用一次，一個任務(wù)也只能用一個機器去完成。需要進行策略選擇，使得完成更多的任務(wù)。

思路：開始想的就是貪心，也想到了貪心的時候時間是主導因素，要優(yōu)先考慮，賽后寫的時候是看的標程用的map來實現(xiàn)的。

?

1 struct node 2 { 3 int time, lev; 4 } a[100010], b[100010]; 5 6 int cmp(node a, node b) 7 { 8 if(a.time == b.time) 9 return a.lev > b.lev; 10 return a.time > b.time; 11 } 12 13 map<int, int> M; 14 int n, m; 15 16 int main() 17 { 18 while(~scanf("%d%d", &n, &m)) 19 { 20 for(int i = 0; i < n; ++i) 21 { 22 scanf("%d%d", &a[i].time, &a[i].lev); 23 } 24 for(int i = 0; i < m; ++i) 25 { 26 scanf("%d%d", &b[i].time, &b[i].lev); 27 } 28 sort(a, a+n, cmp); 29 sort(b, b+m, cmp); 30 M.clear(); 31 int j = 0; 32 int ans1 = 0; 33 long long ans2 = 0; 34 for(int i = 0; i < m; ++i) 35 { 36 while(j < n && a[j].time >= b[i].time) 37 { 38 M[a[j].lev]++; 39 ++j; 40 } 41 map<int, int>::iterator it = M.lower_bound(b[i].lev); 42 if(it != M.end()) 43 { 44 ans1++; 45 ans2 += 500*b[i].time+2*b[i].lev; 46 int t = it->first; 47 M[t]--; 48 if(M[t] == 0) 49 { 50 M.erase(t); 51 } 52 } 53 } 54 printf("%d %I64d\n", ans1, ans2); 55 } 56 57 return 0; 58 } HDU 4864

轉(zhuǎn)載于:https://www.cnblogs.com/Silence-AC/p/3863944.html

總結(jié)

以上是生活随笔為你收集整理的HDU 4864 Task（2014多校--贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。