原题: http://acm.hdu.edu.cn/showproblem.php?pid=4864
大神解题报告: http://www.cnblogs.com/xingxing1024/p/5273176.html#3749458
//hdu 4864 //题目大意:公司现有n个任务要完成，每份任务有它的花费时间xi,等级yi,而公司有m机器,每台机器也有它的限制时间为xi,等级为yi,每台机器只能处理时间和等级都不大于自己的任务 // 每台机器每天只能完成一个任务,每个任务也只能被一个机器完成,完成任务task(xi,yi)可以获得金钱(500*xi+2*yi),已知现在有n个任务和m台机器，公司首先想要保证每天完成最多的任务，如果有许多方案可以满足，那么最多可以赚多少钱？ //思路:这里我们借助一个数组Level[i] 记录等级为i的机器的数量 // ①题目说,每个任务的价值是(500*xi+2*yi), xi(0<xi<1440),yi(0=<yi<=100),所以我们可以知道 只要xi大,则任务的价值就大,所以我们先按价值对任务排序,由大到小 // ②假设有2个任务t1,t2:当遍历到任务t1时，把时间和等级都>=t1的机器加入到level中来,接着在level数组中找等级最接近的机器处理掉t1，成功处理金钱ans增加 // ④当遍历任务t2时，把时间和等级都>=t2的机器加入到level中来,我这里叫他们做"新机器“，上一层留下的旧机器还放在level数组中,如果旧机器无法处理t2（时间绝对是够的,但是可能等级不够）,那么新机器就可以处理t2,如果没有新机器就业无法处理 //为何选择这个方案??按上面的过程,假如mach1处理了t1, 到了t2的时候,如果mach1也可以处理t2,但是t1的价值比t2大，所以可以保证金钱最多,如果mach1不能处理t2，那么就保证了处理的任务最多。所以这个方案是最优的。 //不要使用qsort，否则报错... #include<iostream> #include<cstdio> #include<algorithm> #include<memory.h> using namespace std; typedef long long ll; struct Machine //机器 { ll time; ll level; }mach[100001]; struct Task { ll time; ll level; }task[100001]; int cmp1(Task a,Task b)//按价值从大到小 { if(a.time!=b.time){ return a.time>b.time; }else{ return a.level>b.level; } } int cmp2(Machine a,Machine b)//先按时间再按等级 由大到小 { if(a.time!=b.time){ return a.time>b.time; }else{ return a.level>b.level; } } int level[101]; int main() { int n,m; int i,j; ll k; while(~scanf("%d %d",&n,&m)) { for(i=0;i<n;i++) { scanf("%lld %lld",&mach[i].time,&mach[i].level); } for(i=0;i<m;i++) { scanf("%lld %lld",&task[i].time,&task[i].level); } sort(task,task+m,cmp1); sort(mach,mach+n,cmp2); ll ans=0;//最后的金钱 int cnt=0;//处理的任务数 memset(level,0,sizeof(level)); j=0; for(i=0;i<m;i++) { ll lev=task[i].level; ll time=task[i].time; for(;j<n;j++) { if(mach[j].time>=time) //把时间>=当前任务的添加进来 { level[mach[j].level]++; }else{ break; } } for(k=lev;k<=100;k++)//找>=当前任务等级的机器 { if(level[k]>0) { level[k]--; break; } } if(k<=100)//成功找到 { cnt++; ans=ans+500*time+2*lev; } } printf("%d %lld\n",cnt,ans); } return 0; }这题一开始我的想法：先处理价值大的任务，然后找一个时间和等级都>=这个任务 且最接近的机器去处理它，结果一直超时,因为要给n个任务匹配都需要遍历m个机器,差不多n*m的时间吧,能力也不足想不出什么优化的方法。看了大神的解题报告,先将任务和机器都按时间按大到小排序,这样我们就只需要比较等级这一个变量,用一个level数组记录前n次匹配遗留下的不同等级的机器数目,这些都可能是解决当前任务的机器（因为时间都是大于等于当前任务的）,只需要在其中找一个等级最接近的即可。这样时间最多就是m，我的天，这技巧我真是佩服,十分值得学习。