题解：P11349 [NOISG2024 Finals] Problem Setter

· · 题解

题目大意

有 c 个比赛，每个比赛有最低质量要求 m 和满意度 s，而有 p 个题目，每个题目有质量 q 和负满意度 d，要求将题目上交的同时求得使满意度最大的方案（如果某道题目能拿到的最大满意度不足损失的满意度，则可以不交该题目）。

解题思路

该题本质上就是一道贪心题，对于每一道题目，我们在该题可以提交的所有比赛中（即题目质量满足比赛要求），选择满意度最大的比赛，如果该满意度大于该题上交时损失的满意度（即可以使总满意度变大），则将该题交到该比赛上。

如果直接暴力查找匹配每道题，不用想都知道会超时到怀疑人生。那我们就可以采取带预处理的方法，怎么做呢？

我们可以将所有比赛按题目质量要求从小到大排序，这样在后面查找每道题可以提交的最高质量比赛时，便可以利用有序性，用二分法进行查找把复杂度降到 \log 级别。并且在排好序之后，开一个数组 M，预处理前 i 场比赛的最大满意度，之所以这样写，是因为一旦某道题目满足第 i 场比赛的质量要求，则其必然满足 i 之前所有比赛的质量要求，故在这些比赛里挑出满意度最高的比赛进行提交。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

struct game{ ll m,s; }ga[N];
struct question{ ll q,d; }qu[N];
bool cmp(game &a, game &b){
    return a.m < b.m;
}
ll M[N];

int main(){
    ll c, p,res = 0;
    cin >> c >> p;
    for(int i=1;i<=c;i++) cin >> ga[i].m >> ga[i].s;
    for(int i=1;i<=p;i++) cin >> qu[i].q >> qu[i].d;
    sort(ga+1,ga+c+1,cmp); //排序
    for(int i=1;i<=c;i++) M[i] = max(M[i-1],ga[i].s); //预处理
    for(int i=1;i<=p;i++){
        ll L = 1, R = c;
        ll ind = 0; //ind记录该题目能交到的最高质量要求的比赛
        while(L <= R){ //二分
            ll mid = (L+R)/2;
            if(ga[mid].m <= qu[i].q) ind = mid,L = mid + 1;
            else R = mid - 1;
        }
        if(M[ind] > qu[i].d)res += M[ind]-qu[i].d;//如果这个题目能加大满意度，则加上，否则不交该题目
    }
    cout << res;
    return 0;
}