题解：P11349 [NOISG2024 Finals] Problem Setter

PCSJZ · 2024-12-13 22:23:29 · 题解

思路

贪心，排序。

通过题面，不难发现，当你把题目放到比赛中满意度会增加 s_i - d_j。

所以我们就可以按照增加的满意度进行降序排序，使得 s_i - d_j 尽可能大。

然后就可以判断质量是否合法以及 s_i - d_j 是否大于等于 0。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>

using namespace std;

using ll = long long; // 不要忘记开 long long 
const ll N = 2 * 1e5 + 5;

struct n1 { // 比赛 
    ll m, s;
}a[N];

struct n2 { // 题目 
    ll q, d;
}b[N];

bool cmp(n1 x, n1 y) { // 按照满意度降序排序 
    return x.s > y.s;
}

ll c, p, ans = 0;

int main() {
    scanf("%lld%lld", &c, &p);
    for (int i = 1; i <= c; i++) scanf("%lld%lld", &a[i].m, &a[i].s);
    for (int i = 1; i <= p; i++) scanf("%lld%lld", &b[i].q, &b[i].d);
    sort(a + 1, a + c + 1, cmp);
    for (int i = 1; i <= p; i++) { // 枚举题目 
        for (int j = 1; j <= c; j++) { // 枚举比赛 
            if (b[i].q >= a[j].m && b[i].d <= a[j].s) {
                // 质量是否合法，b[i].d <= a[j].s 可以转化为 a[j].s - b[i].d >= 0，即满意度不为负数 
                ans += a[j].s - b[i].d;
                break;
            }
        }
    }
    printf("%lld", ans);
    return 0;
}