2021 寒假基础第二场 G https://ac.nowcoder.com/acm/contest/9982/G

12 Feb 更新：修正了一处错误，更新了代码。

我们把问题拆成几个，逐个解决：

怎么统计每支队过了多少题？如何统计过了 X 题的有多少支队伍？

这里假设你已经知道差分是啥了，可能第一时间会想到一个 1e9 的数组 diff 作为差分数组，
也就是说，我们使用 diff[i] 表示第 支队伍的过题数和第 支队伍的过题数相差多少。

那么对于每道题给定的 ，使第 到 支队伍的过题数加一，相邻队伍过题数的变化情况无非就两个：

  1. 第 支队伍相比第 支队伍多过了 题，也就是 diff[i]++。
  2. 第 支队伍相比第 支队伍少过了 题，也就是 diff[r+1]--。

接下来我们要求出每个队伍过多少题，只需要前缀和一次就行。
毕竟我们知道没有第 支队伍，所以 diff[1] 其实就是第一支队伍的过题数，首项知道前后项关系也知道自然任意项都能推出来。

但是 1e9 这个数字是在太大了，事实上我们并不需要真的具体到每一支队伍的过题数都需要知道，据个例子：
现在有 20 支队，就两道题，现在告诉你第 支队过了 题，第 支队过了 题。
我们也就关心第 队的情况，因为这些都是边界，他们的过题数与前一支队伍的过题数不同。

具体而言，对于给定的 ，我们只需要记录第 和第 支队伍的过题与前支队伍有和差异就行。
对于其他队伍，我们知道他们跟前一支队伍过题数相同那就足够了，所以我们这里使用的是 map。

map<int, int> diff; // 记录 "关键队伍" 的过题差异信息

int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
    int l, r;
    cin >> l >> r;
    // [l,r] 区间加一，用差分处理
    diff[l] = diff[l] + 1;         // 第 l 支队伍相比第 l-1 支队伍多过了 1 题
    diff[r + 1] = diff[r + 1] - 1; // 第 r+1 支队伍相比第 r 支队伍少过了 1 题
}

现在 题最少 支最多 支 "关键队伍" 的过题差异信息我都已经全部记录下来了，假设我在全部 "关键队伍" 中记录了 diff[a] 和 diff[b]，，然而从第 到 支队伍我一支都没记录（ 和 两支队伍不一定是在同一题被记录的），我们可以得到的信息有：

  1. 从第 支队伍到第 支队伍，一共 支队伍过题数都是一样的。
  2. 基于第 1 点，用第 支队伍的过题数加上 diff[b] 就是第 支队伍的过题数了。

所以即使改用了 map，我们还是用前缀和计算所有关键队伍的实际过题数量。

同时还是基于第 1 点，我们也可以统计统计过了 X 题的有多少支队伍了，由于题目数相对比较少，直接使用数组记录即可。

最后一支 "关键队伍" 以及它后面的队伍是不会纳入 cnt 统计的，也不用专门处理，事实上这也不会影响到答案的：因为这最后一支 "关键队伍" 要不就是不存在的第 支队伍，要不这支队以及它后面的队伍都爆零了（那是肯定没有奖的）。另外因为 map 的特性，遍历 map 肯定是按队伍编号从小到大遍历的，所以放心好了～

int cnt[100010]; // cnt[i] 表示过题数为 i 的队伍数

int lastid = 1; // 记录上一个 "关键队伍" 的编号
int last = 0;   // 记录上一个 "关键队伍" 的过题数量

for (auto &i : diff) // 遍历 map
{
    // i.first 就是遍历到的 "关键队伍" 的编号
    // i.second 就是遍历到的 "关键队伍" 的过题数量
    i.second = i.second + last;    // 前缀和
    cnt[last] += i.first - lastid; // 从第 lastid 到 i.first-1 支队伍的过题数量都是一样的
    last = i.second;
    lastid = i.first;
}

之前的算法入门课练习赛其实有一道很相似的题目，也是 map + 差分，可以去围观一下：

https://ac.nowcoder.com/acm/contest/5773/D

如何知道第 Y​ 名过了多少题？

我们前面使用了 cnt[i] 记录过题数为 的队伍数，其实这些就是边界情况，可以很好地利用。

我们假设现在一共就两题，那么：

  • 从第 1 名到第 cnt[2] 名都过了两题；
  • 从第 cnt[2]+1 名到第 cnt[2]+cnt[1] 名都过了一题；
  • 从第 cnt[2]+cnt[1]+1 名到第 cnt[2]+cnt[1]+cnt[0] 名都爆零了。

那么我们还是使用前缀和，从高过题量到低过题量一路下去，当我们发现 Y 刚好就卡在某个范围内，那么过题数就是它了。

int s = 0;

int l[] = {(int)ceil(1.0 * n / 10), (int)ceil(1.0 * n / 4), (int)ceil(1.0 * n / 2)}; // 现在要求出这些排名过的题目数
int t[] = {1, 1, 1};                                                                 // 求出来后就放到这个数组

for (int i = m; i >= 1; i--) // 从高过题量到低过题量，获奖过题数最低是 1
{
    for (int j = 0; j < 3; j++)
    {
        // 如果 cnt[i] 为 0，那么下面的条件肯定不成立，不用专门考虑
        if (s + 1 <= l[j] && l[j] <= s + cnt[i]) // 把两个边界卡出来，看看 l[j] 在不在这个范围里面
        {
            t[j] = i;
        }
    }
    s += cnt[i]; // 前缀和
}

如何统计金银铜队伍数量？

现在我们已经知道金银铜牌至少需要多少题，那么对于每一个过题数量，我们看看它是否满足金牌的要求，不满足再看看是否满足银牌的要求，不满足再看看是否满足铜牌的要求就行了。输出答案，完结撒花！

int r[] = {0, 0, 0}; // 记录金银铜的队伍数量，也就是答案

for (int i = m; i >= 0; i--)
{
    for (int j = 0; j < 3; j++) // 按照金银铜的顺序逐个试
    {
        if (i >= t[j])
        {
            r[j] += cnt[i];
            break; // 满足高等级奖牌的要求就不用往下试了
        }
    }
}

cout << r[0] << ' ' << r[1] << ' ' << r[2] << endl;

代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46768944