牛牛与比赛颁奖 离散化 差分

本题其实是一道非常基础的离散化+差分的板子题。

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%d ", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
pii a[N];
vector<int> ori;              // 存储原值
unordered_map<int, int> pos;  // key:原值 val: 离散化后
int d[N * 2];                 // 差分数组
int num[N];                   // num[x]表示过x题的队伍数目
int main() {
    int n, m;
    sc(n), sc(m);
    rep(i, 1, m) sc(a[i].first), sc(a[i].second);
    // 离散化
    rep(i, 1, m) {
        ori.emplace_back(a[i].first);
        ori.emplace_back(a[i].second + 1);
    }
    sort(ori.begin(), ori.end());
    ori.erase(unique(ori.begin(), ori.end()), ori.end());
    int sz = ori.size();
    for (int i = 0; i < sz; ++i) pos[ori[i]] = i;
    // 差分
    rep(i, 1, m) {
        d[pos[a[i].first]]++;
        d[pos[a[i].second + 1]]--;
    }
    // 前缀和
    for (int i = 1; i < sz; ++i) d[i] += d[i - 1];
    // 统计过x题的人数
    --sz;
    int maxAcNum = 0;
    for (int i = 0; i < sz; ++i) {
        int acNum = d[i];                   //该区间过题数目
        maxAcNum = max(maxAcNum, acNum);    //更新最多过题数
        int teamNum = ori[i + 1] - ori[i];  //该区间队伍数目
        num[acNum] += teamNum;
    }
    // 计算名额
    int au = (n + 10 - 1) / 10;
    int ag = (n + 4 - 1) / 4;
    int cu = (n + 2 - 1) / 2;
    // 计算答案
    int ans1 = 0, ans2 = 0, ans3 = 0;
    for (int i = maxAcNum; i; --i)  // 要求至少过1题
        if (ans1 < au)
            ans1 += num[i];
        else if (ans1 + ans2 < ag)
            ans2 += num[i];
        else if (ans1 + ans2 + ans3 < cu)
            ans3 += num[i];
    cout << ans1 << ' ' << ans2 << ' ' << ans3;
    return 0;
}

更优雅的做法是直接查询差分的map，这样就省去了离散化的过程，码量很小。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int g[N];
map<int, int> mp;
int num[5];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        mp[x]++, mp[y + 1]--;
    }
    num[1] = (n + 10 - 1) / 10;
    num[2] = (n + 4 - 1) / 4;
    num[3] = (n + 2 - 1) / 2;
    int now = 0, pre = 1, maxn = 0;
    for (auto &i : mp) {  // 遍历差分map
        maxn = max(maxn, now);
        g[now] += i.first - pre;  // 前后位置差值就是这个区间的人数
        now += i.second;  // 加上差分量 差分量就是过题数的位移量
        pre = i.first;
    }
    int ans1 = 0, ans2 = 0, ans3 = 0;
    for (int i = maxn; i; --i)  // 要求至少过1题
        if (ans1 < num[1])
            ans1 += g[i];
        else if (ans1 + ans2 < num[2])
            ans2 += g[i];
        else if (ans1 + ans2 + ans3 < num[3])
            ans3 += g[i];
    cout << ans1 << ' ' << ans2 << ' ' << ans3;
    return 0;
}