宣传一下$\Huge\color{skyblue}{USACO}$月赛打卡活动题解汇总

看到“在l…r之间都加1”就可以想到差分。
差分的时间复杂度为$O(n)$。
然而暴力求解的时间复杂度是$O(n^2)$，显然会超时。
所以我们采取差分的操作。
最后统计出完成后的数组，排序取中位数即可。

#include <bits/stdc++.h>
using namespace std;
int b[1000010];
int main() {
    int n, k; scanf("%d%d", &n, &k);
    for (int i = 1;i <= k; i++) {
        int l, r; scanf("%d%d", &l, &r);
        b[l]++;
        b[r + 1]--;
    }
    for (int i = 1; i <= n; i ++) b[i] += b[i - 1];
    sort(b + 1, b + n + 1);
    printf("%d", b[(n + 1) >> 1]);
    return 0;
}