P10464 Task

iamjcer · 2024-08-20 20:33:54 · 题解

思路

我们通过研究数据范围就可以知道：当 x=1，y=100 时，x，y 分别贡献就是：500 \times 1，2 \times 100，那么我们可以得到结论：哪怕 x 再小，任何时候也不会小于 y 的贡献，可以发现，我们最优策略就是选择满足条件的任务中 x 值越大越好的任务，所以我们可以考虑贪心来做。

怎么贪心呢？

根据上面推出的结论：x 任何时候也不会小于 y 的贡献，那么显然的，我们可以按照 x 作为第一关键字排序，然后 y 作为第二关键字排序，代码如下：

bool cmp(node a,node b){
    if(a.x==b.x) return a.y>b.y;
    else return a.x>b.x; 
}

排完序后，该怎么取求满足条件的任务呢？

看下图：这里可以暴力枚举 m 个任务，然后在用一个指针在 n 个机器人中寻找合法的并进入集合。因为这 n 个机器人是按机器的最大工作时间从大到小排序的，所以只要第 i 个机器人完成不了这个任务，那么第 i+1 个人也不可以完成这个任务，说明具有单调性，根据这个特性，我们可以印证指针遍历这种贪心的合法性。

Code

#include<bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
multiset<int> sset;//定义集合 
multiset<int>::iterator ffind;
struct node{
    int x;
    int y;
}a[N],b[N];
int n,m,second,cnt=0,sum=0;
bool flag=false;
bool cmp(node a,node b){//贪心策略：按 x 作为第一个关键字排序 y 作为第二关键字 
    if(a.x==b.x) return a.y>b.y;
    else return a.x>b.x; 
}
signed main(){
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&a[i].x,&a[i].y);
    }
    for(int i=1;i<=m;i++){
        scanf("%lld %lld",&b[i].x,&b[i].y);
    }
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+m,cmp);
    second=1;//指针初始化 
    for(int i=1;i<=m;i++){
        for(int j=second;j<=n;j++){//从指针往后开始寻找 
            if(flag) break;
            if(a[j].x>=b[i].x){
                sset.insert(a[j].y);//合法的进入集合 
                if(j==n) flag=true;
            }else{
                second=j;
                break;
            }
        }
        ffind=sset.lower_bound(b[i].y);//在集合里面寻找第一个大于等于此时任务等级的机器人等级 
        if((ffind)!=(sset.end())){
            cnt++;
            sum+=500*b[i].x+2*b[i].y;//加上合法贡献值 
            sset.erase(ffind);//把这个值从集合里面删除，避免后面重复使用 
        }
    }
    printf("%lld %lld\n",cnt,sum);
    return 0;
}