【题解】Ntarsis' Set - Codeforces 1852A

出处： Codeforces Round 887

链接： https://codeforces.com/problemset/problem/1852/A

题目大意： 给定一个包含 \(n\) 个正整数的表示删除位置的严格升序序列 \(p\) ，以及另外一个连续正整数的被删除的无穷序列 \(l\) 。进行 \(k\) 次删除操作，每次操作从无穷序列 \(l\) 中同时删除位于第 \(p_1, p_2, \dots, p_n\) 位置的数字，然后未被删除的数字从后往前逐个补齐。求进行完所有的 \(k\) 次删除操作之后，序列 \(l\) 的第一个数字是什么？（具体的含义去原链接看样例说明）

约束： \(1\leq n \leq 2\cdot 10^5\) ， \(1\leq k \leq 2\cdot 10^5\) ， \(1\leq p_i \leq 10^9\) 且 \(p_1 < p_2 < \dots < p_n\)。

PS： 太久不做难的题目了，人变菜了n倍，不过这道题我感觉值得思考的细节还是蛮多的，也希望能帮到需要的人。

解题思路：

1. 确定要使用二分

   先看约束，发现要删除的数字最多为 \(n \cdot k\) 个，然后删除数字的范围最大到 \(k \cdot p_i \leq 10^{14}\) ，不涉及大整数的处理，原题中的 \(10^{1000}\) 只是吓唬人的。

   然后看一下既然直接模拟的 \(O(n\cdot k)\) 的复杂度（可能不止）太高了，自然是退求其次选择把其中一个线性复杂度优化为对数复杂度。这里很明显是需要从 \(n\) 入手因为：其一 \(k\) 是循环次数；其二 \(p\) 是一个有序数组，隐约感觉到能够二分。

2. 确定要二分的是答案

   既然是感觉要二分，对于这道题来说，自然是要二分答案，设答案（进行完所有的 \(k\) 次删除操作之后，序列 \(l\) 的第一个数字）为 \(x\) ，那么思考这个 \(x\)是否满足二分的条件——单调性？

   这里的单调性是：进行完所有的 \(k\) 次删除操作之后， \(x\) 是否还能存在于序列之中？一个小的数字如果被删除了，那么更小的数字是不是被删除的可能性更大，所以满足单调性。想了想会发现有问题，因为删除操作的过程中是会跳过一些头部的数字，对后续的数字进行删除的（下称“跳跃删除”），并不完全满足单调性。这种情况就说明是设置的 \(x\) 的定义不合理，也就是说不能直接设 \(x\) 能不能成为答案，这样会多一个被跳跃删除的判断，从而破坏掉单调性。

   然后既然求“等于”不行，接下来就是二分答案法的神奇套路，改为求“大于等于”或者“小于等于”。对于这道题，是求序列的第一个数字，也就是最小值，那么这里是设置为求“小于等于”。也就是设答案（进行完所有的 \(k\) 次删除操作之后，序列 \(l\) 的第一个数字）能不能小于等于 \(x\) 。设置成这样之后，就不害怕 \(x\) 本身被跳跃删除了，因为如果最后求出“可行”，也就是答案能小于等于 \(x\)，如果 \(x\) 本身被删除了，那么 \(x-1,x-2\) 等等也很可能会成为答案，可以先往下看为什么。

3. 转化成验证问题
   那么问题就转化成了在短时间内验证答案是不是可以大于等于 \(x\) ，做到这里可以用 \(k\) 次循环和长度为 \(n\) 的严格升序序列大概想出一种 \(O(k \cdot logn)\) 的验证方法。也就是每次在严格升序序列中二分 \(x\) 的位置 \(x_p\) （初始值为 \(x\) ，因为这是一个连续正整数序列），求出 \(x\) 之前有多少个元素要被删掉，同时把这些位置删掉之后 \(x\) 的位置 \(x_p\) 也会发生变化，具体而言，如果小于 \(x\) 的元素有 \(delCnt\) 个，那么下一次迭代中 \(x_p=x_p-delCnt\) ，总共循环 \(k\) 次。

   想到这里，就能大概写出程序了。

bool checkX (ll x) {
    ll sumDelCnt = 0;  // <=x 的数字中，总共被删除了几个
    for (int i = 1; i <= k; ++i) {
        // upper_bound 求出 >x 第一个位置，再减1变成 <=x 的最后一个位置
        int delCnt = upper_bound (p + 1, p + 1 + n, x - sumDelCnt) - p - 1;
        sumDelCnt += delCnt;
    }
    return sumDelCnt < x;  // 如果 <=x 的数字中，被删除的数字都至少 >=x ，那么 x 不能成为答案
}

这里的问题变成了各种最烦人的边界问题。也就是各种“大于等于还是大于”，“小于等于还是小于”，“加一还是减一”的问题，这部分细节的处理其实是二分类型的题目乃至是算法竞赛 or LeetCode 的难点所在，这里处理不好的话就前功尽弃了，特别是不能觉得自己“跟标准答案也差不多嘛，我也会了”，这里的边界处理不好就是菜鸟的体现，相反能正常处理的话就说明入门了，能快速想清楚所有的边界的话那就到了精通了。很明显笔者以及来看这篇博文的读者远远不到精通的地步，就得静下心一步一步想清楚并且在旁边写清楚注释是为什么。

这里的细节其实有点难想，就是为什么 $sumDelCnt < x$ 就证明答案可以小于等于 $x$ 了呢，而不用管 $x$ 本身是不是被删掉了？首先如果 $x$ 没有被删掉，那么答案就可以取为 $x$ ，满足答案“小于等于” $x$ 的假设；其次如果 $x$ 真的被删掉了，但却没有导致 $sumDelCnt >= x$ ，则说明存在至少一个小于 $x$ 的数字没有被删掉，那么答案至少是那个数字，当然也满足答案“小于等于” $x$ 的假设。如此循环最终能找到一个最小的 $x_{ans}$ 使得答案“小于等于” $x_{ans}$ ，而比这个 $x_{ans}$ 小的值 $x_v$ ，都会导致 $sumDelCnt >= x_v$ 导致熬不过 $k$ 轮删除就被删掉，答案自然是 $x_ans$ 。

4. 补上起来无关紧要的边界

   作为核心的验证问题解决了，剩下的都是一些无关紧要的小细节。

   首先，熟悉二分的选手很容易可以确定出二分的答案区间 \([L,R]\) 就是 \([1, n \cdot k + 1]\) ；

   然后乘法自然要小心溢出32位int，换用64位int做运算；

   然后这里是用函数 checkX 检查中点 \(M = (L+R)/2\) 可不可行，如果可行的话当然是移动之后仍然要包含当前的值，然后猜测更小的值是不是可行，自然是 \(R=x\) ，否则如果不可行的话自然要抛弃这个值 \(L=x+1\) ，由于这种算法是 \(L\) 移动至少1步，而 \(R\) 可能不会移动，所以在二分的时候取的中间点 \(M\) 是取下整；这一点感觉很多缺乏经验的选手可能会弄错，分不清楚什么时候取下整什么时候取上整；尤其是针对存在负数的情况，一不小心就会死循环。这里我的建议是对于正整数来说就区分是 \(L\) 一定移动还是 \(R\) 一定移动，然后区分要不要改成取上整；而对于负数来说，则在 \(R-L\leq 2\) 或者 \(R-L\leq 3\) 的时候进行 break ，然后根据自己需要的是最大值还是最小值进行一次 for 循环检查。

完整代码：

const int MAXN = 2e5 + 5;

int n, k;
int p[MAXN];

bool checkX (ll x) {    // 不要溢出
    ll sumDelCnt = 0;   // <=x 的数字中，总共被删除了几个
    for (int i = 1; i <= k; ++i) {
        // upper_bound 求出 >x 第一个位置，再减1变成 <=x 的最后一个位置
        int delCnt = upper_bound (p + 1, p + 1 + n, x - sumDelCnt) - p - 1;
        sumDelCnt += delCnt;
    }
    return sumDelCnt >= x;  // 如果 <=x 的数字中，被删除的数字都至少 >=x ，那么 x 不能成为答案
}

void solve() {
    RD (n, k);
    RDN (p, n);

    ll L = 1LL, R = 1LL * n * k + 1;    // 删除了 n * k 次，至少为 n * k + 1 ，不要溢出
    while (L < R) {
        ll M = (L + R) >> 1;    // 由于下文中移动的是 L ，所以这里计算 M 的时候取下整，不要溢出
        if (checkX (M)) {
            L = M + 1;
        } else {
            R = M;
        }
    }

    WT (L); // 这种写法的二分，最终答案 L == R ，可以任选一个进行输出
}