C. Ntarsis' Set
(\(1 \leq n,k \leq 2 \cdot 10^5\))
题解：思维 + 二分
- 我们不妨反向考虑
- 由于答案最后一次一定在第一个位置
- 所以答案上一轮一定在第一个空的位置，假设这个位置为\(x\)
- 那么如果说要使得答案在位置\(x\)，那么上上一轮答案一定在第\(x\)个空的位置
- 我们可以预处理空位置数量的前缀和
- 然后枚举\(k\)即可，每次枚举二分找到空位置
const int N = 2e5 + 10, M = 4e5 + 10;
int n, k;
int a[N];
int pre[N];
void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
pre[i] = pre[i - 1] + a[i] - a[i - 1] - 1;
}
if (a[1] > 1)
{
cout << 1 << endl;
return;
}
int ans = 1;
for (int i = 1; i <= k; ++i)
{
int p = lower_bound(pre + 1, pre + n + 1, ans) - pre;
ans = a[p - 1] + (ans - pre[p - 1]);
}
cout << ans << endl;
}