AcWing 127. 任务
原题链接
困难
作者:
开心小子
,
2019-10-21 22:44:22
,
所有人可见
,
阅读 984
//首先本题是一个典型的点对点的问题
//我们首先要考虑完成的数目
//然后在考虑效益的问题
//让我们在细细研究一下效益的问题,首先每个任务的效益是固定的
//令外根据难度级别和完成时间对效益的影响,其中其决定的影响是
//完成时间
//那我们就可以将任务和机器都分别以完成时间为第一关键字和难度级别
//为第二关键字,进行降序排序
//并进行降序的遍历任务让更多先遍历到的任务更够执行,则可以获得
//最高的价值
//利用贪心的算法我们可以找到很多种(最多完成任务数)的情况
//而经过排序之后,我们找到的就是这其中完成时间总和最大的情况
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int ,int > pii;
const int maxn=100010;
pii mchs[maxn],tasks[maxn];
int n,m;
int main(){
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
cin>>mchs[i].first>>mchs[i].second;
for(int j=0;j<m;j++)
cin>>tasks[j].first>>tasks[j].second;
sort(mchs,mchs+n);
sort(tasks,tasks+m);
ll cnt=0,res=0;
multiset<int > sy;
//用于存储能够完成当前任务的机器
for(int i=m-1,j=n-1;i>=0;i--)
{
//类似于由大到小遍历任务是否能完成
auto x=tasks[i].first,y=tasks[i].second;
while(j>=0&&mchs[j].first>=x)//满足可以完成当前任务的时间条件时
sy.insert(mchs[j--].second);
auto it=sy.lower_bound(y);
//利用贪心的思想在能完成任务的条件下选择最小的难度等级的机器
if(it!=sy.end())
{
cnt++;
res+=500*x+2*y;
sy.erase(it);
}
}
cout<<cnt<<' '<<res<<endl;
}
return 0;
}