題目鏈接:Task
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 893 Accepted Submission(s): 201
Input The input contains several test cases.
Output For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.
Sample Input 1 2 100 3 100 2 100 1
Sample Output 1 50004
Source 2014 Multi-University Training Contest 1
題意:
有n個機器,m個任務。每個機器至多能完成一個任務。對於每個機器,有一個最大運行時間xi和等級yi,對於每個任務,也有一個運行時間xj和等級yj。只有當xi>=xj且yi>=yj的時候,機器i才能完成任務j,並獲得500*xj+2*yj金錢。問最多能完成幾個任務,當出現多種情況時,輸出獲得金錢最多的情況。
分析:
從一開頭就知道了貪心的基本思路。就是先將任務和機器按降序排列(先時間,時間相同再按難度),然後采用貪心求解。當時腦洞太大,先選擇機器,再選擇該機器能完成的最大利潤的任務,但是選擇下一個機器的時候,忘了考慮被上一個機器忽略的那些任務,導致無限WA,到最後才想到有這一茬。網上給的題解是先選任務然後再選適合的最小機器。按照題解稍微修改了自己的代碼然後AC了,其實和先選機器的思想是一致的,唉,太水無能。
代碼:
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 #define maxn 100010 8 struct node{ 9 int tm, dif; 10 }MCH[maxn], TSK[maxn]; 11 12 bool cmp(node a, node b) 13 { 14 if(a.tm==b.tm) return a.dif > b.dif; 15 return a.tm > b.tm; 16 } 17 int main() 18 { 19 int n, m; 20 while(~scanf("%d%d", &n, &m)) 21 { 22 for(int i = 1; i <= n; i++) 23 scanf("%d%d", &MCH[i].tm, &MCH[i].dif); 24 for(int i = 1; i <= m; i++) 25 scanf("%d%d", &TSK[i].tm, &TSK[i].dif); 26 sort(MCH+1, MCH+n+1, cmp); 27 sort(TSK+1, TSK+m+1, cmp); 28 int cnt = 0, c[102]; 29 __int64 sum = 0; 30 memset(c, 0, sizeof(c)); 31 for(int i = 1, j = 1; i <= m; i++) 32 { 33 while(j <= n && MCH[j].tm >= TSK[i].tm) 34 { 35 c[MCH[j].dif]++; 36 j++; 37 } 38 for(int k = TSK[i].dif; k <= 100; k++) 39 { 40 if(c[k]) 41 { 42 cnt++; 43 c[k]--; 44 sum += 500*TSK[i].tm+2*TSK[i].dif; 45 break; 46 } 47 } 48 } 49 printf("%d %I64d\n", cnt, sum); 50 } 51 return 0; 52 }
www.cnblogs.com/...1.html
看看這個網站,博主有QQ,可以請教呀。
打表吧,0秒過的應該是用這個方法,偶猜想可能用自動機做