# 工厂机器安排(贪心)

### 题目描述

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.

### 现在介绍两种解法

``````#include<stdio.h>
#include<algorithm>
using namespace std;
struct machine
{
int x,y;//x为时间，y为等级
};
{
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;
}
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];
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;
}``````

``````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);``````

``````struct singletask
{
int x;//x为时间
};
{
int num;//记录这个等级的任务的数量
{
num=0;
}
};
//（需要比较的两个任务等级一定相同）按任务的时间排序
{
return a.x<b.x;
}
//leveltas[i]为等级为i的任务的存储序列
//排序
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为等级
};
{
int x;//x为时间
};
{
int num;//记录这个等级的任务的数量
{
num=0;
}
};
bool cmp1(machine a,machine b)
//按机器的等级升序排序，等级相同按时间降序排序
{
if(a.y==b.y)
return a.x>b.x;
else
return a.y<b.y;
}

//（需要比较的两个任务等级一定相同）按任务的时间排序
{
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];
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;
}``````