题目传送门
【题目大意】
有$m$个任务，第$i$个任务等级为$y_i$，完成任务需要的时间为$x_i$，收益为$500*x_i+2*y_i$。有$n$台机器，第$i$台机器的等级为$y_i$，最长工作时间为$x_i$，如果任务等级高于机器等级或是任务时间大于机器工作时间，则不能用该机器完成该任务。一台机器只能完成一个任务，一个任务也只能在一台机器上完成，求最多可以完成多少个任务并求出最大收益。
【思路分析】
这题的贪心虽然很明显，但有点难想，因为时间在收益中所占的比重更大，所以考虑以时间为第一关键字，等级为第二关键字分别给任务和机器从大到小排序。然后枚举每个任务，记录每个满足时间条件的机器，再从小到大查找满足等级条件的机器并计算收益。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #define rg register 6 #define go(i,a,b) for(rg int i=a;i<=b;i++) 7 #define ll long long 8 using namespace std; 9 const int N=100002; 10 int n,m,num[102],ans1; 11 ll ans2; 12 struct machine{ 13 int x,y; 14 }a[N],b[N]; 15 bool cmp(machine A,machine B){ 16 if(A.x!=B.x) return A.x>B.x; 17 return A.y>B.y; 18 } 19 int main(){ 20 while(scanf("%d%d",&n,&m)!=EOF){ 21 go(i,1,n) scanf("%d%d",&a[i].x,&a[i].y); 22 go(i,1,m) scanf("%d%d",&b[i].x,&b[i].y); 23 sort(a+1,a+1+n,cmp);sort(b+1,b+1+m,cmp); 24 int j=1; 25 go(i,1,m){ 26 while(j<=n&&a[j].x>=b[i].x) num[a[j].y]++,j++; 27 //记录满足时间条件的机器 28 go(k,b[i].y,100) 29 if(num[k]){//查找满足等级条件的机器 30 num[k]--;ans1++;ans2+=500*b[i].x+2*b[i].y; 31 break; 32 } 33 } 34 printf("%d %lld\n",ans1,ans2); 35 ans1=ans2=0;memset(num,0,sizeof(num)); 36 } 37 return 0; 38 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11272747.html
