题目传送门：Codeforces 1852A Ntarsis' Set
题意
给定一个集合，里面初始有 \(1,2,3...10^{1000}\)，告诉你每天会拿掉其中的第 \(a_1, a_2, a_3 ...a_n\) 个，询问这样的 \(k\) 天之后剩下的最小的数是多少。
分析
-
思考如果 \(x\) 在这天没有被删掉，那么哪些被删掉的位置会对它产生什么样的影响
解答：如果 \(a_i < pos_{x} < a_{i + 1}\) ，那么他会移动到 \(pos_x - i\) 的位置
-
带着这个发现，去反向模拟
题解
首先我们运用逆向思维，不去直接模拟删除元素，而是模拟插入 \(0\) 的过程，其中每一轮将 \(0\) 插入要删除的位置，即 $ a_i - i$ ，这样操作 \(k\) 天后，1出现的位置即为输出结果。
如何模拟这个过程呢？我们可以简化这个思路，第一个 \(1\) 之后插入的 \(0\) 是对答案没有贡献的，因此我们只需要计算哪些插入对答案有贡献即可，如何计算数值在第几天之后有贡献呢：
- 如果第一个元素是 \(1\) ，那么第一天就会有贡献
- 如果第二个元素是 \(2\) ，那么第二天会有贡献
- 如果第二个元素是 \(4\) ，那么第四天会有贡献
- 推广至第 \(inc\) 个元素，设当前 \(1\) 的位置为 \(ans\) ，那么还需要
(a[inc] - ans + inc - 1) / inc天才能有贡献
AC代码
#include <bits/stdc++.h>
using namespace std;
int n, k, a[200010];
void solve() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i] -= i;
}
if (a[0] != 1) {
cout << 1 << "\n";
return;
}
a[n] = 2e9;
//start at position 1, and find what number moves to its position
long long ans = 1;
int inc = 1; //how many zeroes to insert
while (inc < n) {
int days = (a[inc] - ans + inc - 1) / inc; // 需要多少天才能有效贡献
if (days >= k){ // k不足，计算之前的元素可以贡献的有效的插入的0
ans += k * inc;
k = 0;
break;
}
ans += days * inc; // k充足，计算总贡献
k -= days; // 这里 - days，表示 花费的轮数
// 小于的元素，表示已经被前面的其他元素覆盖，没起作用
while (a[inc] <= ans) inc++;
}
ans += 1ll * k * n; // 剩下的k轮，每次可以插入n个0,走n步
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int t; cin >> t;
while (t--) solve();
}