题解:P10464 Task

24 年 10 月 9 日 星期三
128 字
1 分钟

简单贪心。由于时间对收入的影响远大于级别对收入的影响,故优先考虑时间再考虑级别进行排序。然后逆序枚举每个任务,每次选择能满足当前任务所需时间的机器中级别最低的一台即得最优方案。

代码

cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,M=1e2+50;
struct Node{ll x,y;}a[N],b[N];
ll n,m,i,j,pos,x,s,ans,f[M];
int main(){
	cin>>n>>m;
	for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	for(i=1;i<=m;i++)cin>>b[i].x>>b[i].y;
    stable_sort(a+1,a+1+n,[](Node x,Node y){return x.x!=y.x?x.x>y.x:x.y>y.y;});
    stable_sort(b+1,b+1+m,[](Node x,Node y){return x.x!=y.x?x.x>y.x:x.y>y.y;});
	for(i=1;i<=m;i++){
		for(j=pos+1;j<=n;j++)
			if(a[j].x>=b[i].x)f[a[j].y]+=1,pos=j;
			else break;
		for(x=b[i].y;x<=100;x++)
			if(f[x]){
				s++;ans+=b[i].x*500+b[i].y*2;f[x]--;
				break;
			}
	}
	cout<<s<<' '<<ans;
}

文章标题:题解:P10464 Task

文章作者:Walter_Fang

文章链接:https://blog.walterfang.us.kg/posts/solution-p10464[复制]

最后修改时间:


商业转载请联系站长获得授权,非商业转载请注明本文出处及文章链接,您可以自由地在任何媒体以任何形式复制和分发作品,也可以修改和创作,但是分发衍生作品时必须采用相同的许可协议。
本文采用CC BY-NC-SA 4.0进行许可。