出处： 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倍，不过这道题我感觉值得思考的细节还是蛮多的，也希望能帮到需要的人。
解题思路：
- 先看约束，发现要删除的数字最多为 \(n \cdot k\) 个，然后删除数字的范围最大到 \(k \cdot p_i \leq 10^{14}\) ，不涉及大整数的处理，原题中的 \(10^{1000}\) 只是吓唬人的。
- 然后看一下既然直接模拟的 \(O(n\cdot k)\) 的复杂度（可能不止）太高了，自然是退求其次选择把其中一个线性复杂度优化为对数复杂度。这里很明显是需要从 \(n\) 入手因为：其一 \(k\) 是循环次数；其二 \(p\) 是一个有序数组，隐约感觉到能够二分。
- 既然是感觉要二分，对于这道题来说，自然是要二分答案，设答案（进行完所有的 \(k\) 次删除操作之后，序列 \(l\) 的第一个数字）为 \(x\) ，那么思考这个 \(x\)是否满足二分的条件——单调性？
- 这里的单调性是：进行完所有的 \(k\) 次删除操作之后， \(x\) 是否还能存在于序列之中？一个小的数字如果被删除了，那么更小的数字是不是被删除的可能性更大，所以满足单调性。想了想会发现有问题，因为删除操作的过程中是会跳过一些头部的数字，对后续的数字进行删除的（下称“跳跃删除”），并不完全满足单调性。这种情况就说明是设置的 \(x\) 的定义不合理，也就是说不能直接设 \(x\) 能不能成为答案，这样会多一个被跳跃删除的判断，从而破坏掉单调性。
- 然后既然求“等于”不行，接下来就是二分答案法的神奇套路，改为求“大于等于”或者“小于等于”。对于这道题，是求序列的第一个数字，也就是最小值，那么这里是设置为求“大于等于”。也就是设答案（进行完所有的 \(k\) 次删除操作之后，序列 \(l\) 的第一个数字）能不能大于等于 \(x\) 。设置成这样之后，就不害怕 \(x\) 本身被跳跃删除了，因为如果最后求出“可行”，也就是答案能大于等于 \(x\)，如果 \(x\) 本身被删除了，那么 \(x+1,x+2\) 等等也能顺次成为答案。
- 那么问题就转化成了在短时间内验证答案是不是可以大于等于 \(x\) ，做到这里可以用 \(k\) 次循环和长度为 \(n\) 的严格升序序列大概想出一种 \(O(k \cdot logn)\) 的验证方法。也就是每次在严格升序序列中二分 \(x\) 的位置 \(x_p\) （初始值为 \(x\) ，因为这是一个连续正整数序列），求出 \(x\) 之前有多少个元素要被删掉，同时把这些位置删掉之后 \(x\) 的位置 \(x_p\) 也会发生变化，具体而言，如果小于 \(x\) 的元素有 \(i\) 个，那么下一次迭代中 \(x_p=x_p-i\) ，总共循环 \(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 不能成为答案
}
- 这里的问题变成了各种最烦人的边界问题。也就是各种“大于等于还是大于”，“小于等于还是小于”，“加一还是减一”的问题，这部分细节的处理其实是二分类型的题目乃至是算法竞赛/写LeetCode的难点所在，这里处理不好的话就前功尽弃了，特别是不能觉得自己“跟标准答案也差不多嘛，我也会了”，这里的边界处理不好就是菜鸟的体现，相反能正常处理的话就说明入门了，能快速想清楚所有的边界的话那就到了精通了。很明显笔者以及来看这篇博文的读者远远不到精通的地步，就得静下心一步一步想清楚并且在旁边写清楚注释是为什么。