HDU-4864 Task
题面
有N个机器与M个任务,每个机器或者任务都有两个属性(x,y)
(N <= 100000, M <= 100000, 0 < x <1440, 0<=y <= 100)
机器的x表示这个机器的最长工作时间, y表示机器的等级
任务的x表示完成这个任务需要花费的时间,y表示任务的等级
每个机器只能做一个任务,机器的等级必须大于等于任务的等级
每完成一个任务可以获得500x+2y的价值(x,y是任务的x,y)
请问最多可以完成多少个任务以及在此基础上最多可以获得多少的价值
总结
一开始我们可以将这些点都放在一个平面直角坐标系中，一台机器能完成的任务都位于自己的左下方：
因为价值的计算公式是500 \times x + 2 \times y，x 的影响明显比 y 大（而且y \times 2 \leq 200 \leq 500），所以我们可以将任务按照x降序排序，为了方便后续操作，我们也可以在x相同时按照y降序排序。
我们同时从头开始遍历任务和机器，对于每一个任务，我们找出所有符合要求的机器（因为是降序排序的，所以找到一个x值不符合要求的机器后即可停止遍历），接下来寻找一个y值最接近于任务的机器（因为奖励只与任务有关，机器尽可能靠近以免浪费）。
槽点
- 一直读取直到结束的代码应该是这样子的：
while(~scanf("%d%d",&n,&m)){
- 这道题要求输出两个数，而忘记输出“最多可以完成多少个任务”。
AC代码
#include<bits/stdc++.h>
using namespace std;
pair<int,int> mi[200000],ni[200000];
int m,n,a,b,minn,minni,cnt[200],cans;
long long ans;
bool flag[200000];
inline bool cmp(pair<int,int> a,pair<int,int> b){
return a.first==b.first ?a.second>b.second:a.first>b.first;
}
int main(){
while(~scanf("%d%d",&n,&m)){
memset(cnt,0,sizeof(cnt));
ans=cans=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&b);
ni[i]=make_pair(a,b);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
mi[i]=make_pair(a,b);
}
sort(ni+1,ni+n+1,cmp);
sort(mi+1,mi+m+1,cmp); //m:Task ; n:Machine
for(int i=1,j=1;i<=m;i++){ //i:Task ; j:Machine
while(j<=n&&ni[j].first>=mi[i].first){
cnt[ni[j].second]++;
j++;
}
minn=1000;
for(int jj=mi[i].second;jj<=100;jj++){
if(cnt[jj]){
cans ++;
ans = ans + 500*mi[i].first+2*mi[i].second;
cnt[jj]--;
break;
}
}
}
printf("%d %lld\n",cans,ans);
}
return 0;
}