题目描述
Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500xi+2yi) dollars.
The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.
The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.
输入格式
The input contains several test cases.
The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).
The following N lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the maximum time the machine can work.yi is the level of the machine.
The following M lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the time we need to complete the task.yi is the level of the task.
输出格式
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.
这道题的大意是给定每一个机器和任务，都有两个属性——时间和等级。当且仅当一个机器的时间和等级分别大于某一个任务时，这个任务才能被这个机器所完成。另外一个任务只能被一个机器完成，一个机器一天只能执行一个任务。每当一个任务被完成时将会得到(500*任务时间+2*任务等级)的美刀的报酬。现给出若干机器和任务，求出最大盈利。
现在介绍两种解法
解法一
这种解法是网上给出的最常见的解法。
首先是要对所有任务进行时间降序（时间相同按难度降序）的排序，其目的是保证，能完成前一个任务的机器一定能完成后面的任务。因此只需要在执行每一个任务之前找全所有能完成该任务的机器即可。
此算法是只需要记录能够完成这个任务的机器的数量，并且按照机器的等级进行存储。由于能完成前一个任务的机器一定能完成后面的任务，因此对于任意一个任务，能完成该任务的机器数量==(原先能完成前一个任务的机器数+新增的能完成该任务的机器数)。更新完可行的机器数量之后，就可以在其中找到一台能够完成的机器即可，由于我们要保证尽可能多的实现利润，所以要选择等级尽可能低的机器，因为时间条件都满足的机器，等级高的机器一定能完成等级低的机器所能完成的任务，反之不行。
代码如下：
#include<stdio.h>
#include<algorithm>
using namespace std;
struct machine
{
int x,y;//x为时间，y为等级
};
struct task
{
int x,y;//x为时间，y为等级
};
bool cmp1(machine a,machine b){
if(a.x==b.x)
return a.y>b.y;
else
return a.x>b.x;
}
bool cmp2(task a,task b){
if(a.x==b.x)
return a.y>b.y;
else
return a.x>b.x;
}
int main ()
{
int m,n;
long long ans=0,num=0;
scanf("%d%d",&n,&m);
machine mach[n+1];
task tas[m+1];
for (int i=0;i<n;i++)
{
scanf("%d%d",&mach[i].x ,&mach[i].y);
}
for (int i=0;i<m;i++)
{
scanf("%d%d",&tas[i].x ,&tas[i].y);
}
//按时间降序排序，若时间相同则按等级降序
sort(mach,mach+n,cmp1);
sort(tas,tas+m,cmp2);
int c[105] = {0};
//c[k]数组是等级为k的且时间大于当前任务时间的空闲机器数量
for(int i = 0,j = 0; i<m; i++)
{
//对于第i个任务
while(j<n && mach[j].x>=tas[i].x)
//遍历剩余未遍历的机器，如果能做这个任务，就将其记录到数组c[]中
{
c[mach[j].y]++;
j++;
}
//选择一台能够完成此任务的机器
for(int k = tas[i].y; k<=100; k++)
//从当前机器等级==任务等级的开始选，如果没有就增加机器的等级
{
if(c[k])
{
c[k]--;//找到一台可以做此任务的机器后，该等级的机器数--
ans+=(tas[i].x*500+tas[i].y*2);
num++;
break;
}
}
}
printf("%lld %lld",num,ans);
return 0;
}该算法的复杂度为O(n+m)。
解法二
声明：此方法是我个人研究所得，数据结构复杂且效率没有上一种方法高，请有选择地加以阅读！
同样的思路，即时间条件都满足的机器，等级高的机器一定能完成等级低的机器所能完成的任务，反之不行。那么我们只需要将等级低的机器优先选择其能完成的任务，后让等级高的选择即可。
对于每一个机器，由于需要让等级低的有限选择，所以按照等级升序，相同等级按照时间降序的方式排序：
struct machine
{
int x,y;//x为时间，y为等级
};
bool cmp1(machine a,machine b)
//按机器的等级升序排序，等级相同按时间降序排序
{
if(a.y==b.y)
return a.x>b.x;
else
return a.y<b.y;
}
//排序
sort(mach,mach+n,cmp1);对于一个等级为 i 的机器，它可以选择的任务的等级范围为 j (0<=j<=i) ，为了运行提高效率，可以将所有任务按照等级分别存储。对于每一个任务等级 j (0<=j<=i) ，有利润最大值 ans(j) (0<=j<=i) ,那么该机器可以实现的最大利润就是MAX(ans(j))。
所以对于每一个任务，需要按照等级来分别存储，并且相同等级的任务要按照时间升序排序（遍历时从后向前）：
struct singletask
{
int x;//x为时间
};
struct leveltask
{
singletask tas[2000];//记录这个等级的所有任务的所需时间
int num;//记录这个等级的任务的数量
leveltask()//将数量初始化为0
{
num=0;
}
};
bool cmp2(singletask a,singletask b)
//（需要比较的两个任务等级一定相同）按任务的时间排序
{
return a.x<b.x;
}
//leveltas[i]为等级为i的任务的存储序列
leveltask leveltas[105];
//排序
for (int i=0;i<105;i++){
//每一个等级如果不为空就需要排序
if (leveltas[i].num){
sort(leveltas[i].tas,leveltas[i].tas+leveltas[i].num,cmp2);
}
}这些处理工作完成之后，就可以寻找每一个机器可以实现的最大利润了：
for (int i=0;i<n;i++)
//选择一个机器
{
// chosen_lvl为最终选择的任务的等级，chosen_num为最终选择的任务在存储序列中的序号，chosen_ans为最终可实现的最大利润
int chosen_lvl=-1,chosen_num=-1,chosen_ans=0;
for (int level=0;level<=mach[i].y;level++)
//遍历所有的可选的任务等级
{
for (int j=leveltas[level].num-1;j>=0;j--)
//从后向前访问每一个任务的时间（时间从大到小）
{
if (leveltas[level].tas[j].x<=mach[i].x)
//如果可以执行
{
int temp=500*leveltas[level].tas[j].x+2*level;
if (temp>chosen_ans)
//和目前最大利润比较，如果更大就更新
{
chosen_lvl=level;
chosen_num=j;
chosen_ans=temp;
}
break;
}
}
}
if (chosen_lvl!=-1)
//chosen_lvl==-1时表示该机器不能执行任何任务
{
ans+=chosen_ans;//ans为总利润
for (int j=chosen_num;j<leveltas[chosen_lvl].num;j++)
//将刚刚所选的任务从序列中移除
{
leveltas[chosen_lvl].tas[j].x=leveltas[chosen_lvl].tas[j+1].x;
}
//这个等级的任务数量-1
leveltas[chosen_lvl].num--;
num++;//num为总执行任务数量
}
}完整代码如下：
#include<stdio.h>
#include<algorithm>
using namespace std;
struct machine
{
int x,y;//x为时间，y为等级
};
struct singletask
{
int x;//x为时间
};
struct leveltask
{
singletask tas[2000];//记录这个等级的所有任务所需时间
int num;//记录这个等级的任务的数量
leveltask()//将数量初始化为0
{
num=0;
}
};
bool cmp1(machine a,machine b)
//按机器的等级升序排序，等级相同按时间降序排序
{
if(a.y==b.y)
return a.x>b.x;
else
return a.y<b.y;
}
bool cmp2(singletask a,singletask b)
//（需要比较的两个任务等级一定相同）按任务的时间排序
{
return a.x<b.x;
}
int main ()
{
int m,n;
int x,y,tasknum=0;
long long ans=0,num=0;
scanf("%d%d",&n,&m);
machine mach[n+1];
leveltask leveltas[105];
for (int i=0;i<n;i++)
{
scanf("%d%d",&mach[i].x ,&mach[i].y);
}
for (int i=0;i<m;i++)
{
scanf("%d%d",&x ,&y);
leveltas[y].tas[leveltas[y].num++].x=x;
}
sort(mach,mach+n,cmp1);
for (int i=0;i<105;i++)
//每一个等级如果不为空就需要排序
{
if (leveltas[i].num)
{
sort(leveltas[i].tas,leveltas[i].tas+leveltas[i].num,cmp2);
}
}
for (int i=0;i<n;i++)
//选择一个机器
{
// chosen_lvl为最终选择的任务的等级，chosen_num为最终选择的任务在存储序列中的序号，chosen_ans为最终可实现的最大利润
int chosen_lvl=-1,chosen_num=-1,chosen_ans=0;
for (int level=0;level<=mach[i].y;level++)
//遍历所有的可选的任务等级
{
for (int j=leveltas[level].num-1;j>=0;j--)
//从后向前访问每一个任务的时间（时间从大到小）
{
if (leveltas[level].tas[j].x<=mach[i].x)
//如果可以执行
{
int temp=500*leveltas[level].tas[j].x+2*level;
if (temp>chosen_ans)
//和目前最大利润比较，如果更大就更新
{
chosen_lvl=level;
chosen_num=j;
chosen_ans=temp;
}
break;
}
}
}
if (chosen_lvl!=-1)
//chosen_lvl==-1时表示该机器不能执行任何任务
{
ans+=chosen_ans;
for (int j=chosen_num;j<leveltas[chosen_lvl].num;j++)
//将刚刚所选的任务从序列中移除
{
leveltas[chosen_lvl].tas[j].x=leveltas[chosen_lvl].tas[j+1].x;
}
//这个等级的任务数量-1
leveltas[chosen_lvl].num--;
num++;
}
}
printf("%lld %lld",num,ans);
return 0;
}总结：
第二种方法只是思路简单，实际上效率不高，我优化了很久才能通过所有测试样例。