本文共 2286 字，大约阅读时间需要 7 分钟。

题意：有n个机器和m个任务，每个机器每天都有一个最大工作时长x1，以及最大工作难度y1，每个任务都有一个工作时间x2，工作难度y2。每完成一个任务多有一个收益500×x2+2×y2。假设每个机器一天只能完成一个任务，一个任务只能又一个机器完成，不可由多个一起完成。求一天当中能完成的最多任务，并输出收益。若有多种情况，输出最大的收益。

限制条件：1<=n,m<=100000；1<=x1,x2<=1440；1<=y1,y2<=100。

分析：

这道题的难点在于，对于每个机器都有两个指标去影响它的任务分配，即时间x1>=x2?和难度y1>=y2?一开始想找个权值，能够同时衡量两个指标，但很遗憾没能找到，或者根本不存在，于是在网上看了牛人的思路，觉得十分巧妙，应向牛人学习。

贪心策略：能够完成任务的条件是x1>=x2，y1>=y2，因此，对于每个任务，我们要优先选出那个可接受的工作时间，工作难度都比它大，而且可接受的工作难度最接近它的机器。

先设置一个结构体node，包含时间t，难度l两个成员，开辟mach[]，task[]两个数组，两个数组都按t从大到小排，t同则按l从大到小排序，同时，开辟辅助数组level[101]（关键），level[]的下标表示工作的难度，是有意义的，数组元素初始化为0。 第一步：设i，j分别为任务，机器的下标，对于第i个任务，我们找出所有mach[j],t>=task[i].t的机器，记录下满足此条件的机器的工作难度的个数，也就是说level[mach[j].l]++；当mach[j].t<task[i].t时，停止寻找。然后对于第i+1个任务，我们不必再从头的遍历一遍，只需从上一次的j开始寻找即可，因为我们mach，task都已经从大到小排序了，因此j之前满足第i个任务，一定也满足第i+1个任务，不必再重复扫描一边前面的机器了。 第二步：设置一个循坏，从level[]中找出第一个比task[i].l大的，也就是最接近它的机器出来，如何实现，看后面的代码。

伪代码如下（主要写第一步和第二步的实现）：

for(i=0,j=0;i<=m-1;i++) //i，j分别表示任务和机器的下标。 { while(j<n&&mach[j].t>=task[i].t){ //表示找到了时间大于任务的机器 k=mach[j].l; level[k]++; //记录下满足条件的机器中，难度为k的有多少个 j++; } for(k=task[i].l;k<=100;k++){ k从task[i],l开始，连续递增1，这样就能确保找到了难度最接近该任务的机器了 if(level[k]!=0) //不为0，说明有满足条件的机器 { cnt++;ans+=…; level[k]- -; //注意！用过了，就要-1 break; //注意！分配好了，就要结束！ } }

代码如下：

#include
   
    #include
    
     #include
     
      using namespace std;struct node{	int t;	int l;}task[100005],mach[100005];int level[101];bool cmp(node x,node y){	if(x.t!=y.t)	    return x.t>y.t;	return x.l>y.l;}int main(){	int n,m;	int i,j,k;	long long ans,cnt;	while(~scanf("%d %d",&n,&m))	{		ans=cnt=0;		for(i=0;i<=n-1;i++)		    scanf("%d %d",&mach[i].t,&mach[i].l);		for(i=0;i<=m-1;i++)		    scanf("%d %d",&task[i].t,&task[i].l);		sort(mach,mach+n,cmp);		sort(task,task+m,cmp);		memset(level,0,sizeof(level));		for(i=0,j=0;i<=m-1;i++)		{			while(j
      
       =task[i].t)			{				level[mach[j].l]++;				j++;			}			for(k=task[i].l;k<=100;k++)			{				if(level[k]!=0)				{					cnt++;					ans+=500*task[i].t+2*task[i].l;					level[k]--;					break;				}			}		}		printf("%lld %lld\n",cnt,ans);	}	return 0;}
      
     
    
   

小结：

1.此题十分巧妙之处就是，引入了一个辅助数组level，并赋予了level下标具体的意义，这是很抽象但又很巧秒的做法（跟dp有点类似）。 2.此题的贪心策略比较的复杂，首先先考虑时间，其次考虑难度，而且，对于难度这项指标，要选择比任务大且最接近它的，这样做的原因是为了让后面的任务更加有可能被分配上。但对于时间是没有必要这样的。两句话概括，时间确定后，难度就成了关键。 3.此题另外一个有收获的地方就是，结构体的运用，bool cmp函数的运用，以及它们与sort函数的运用，具有很大的参考意义。

转载地址：http://nfdci.baihongyu.com/