题目大意
集合 \(S:1,2,3,4,\dots,10^{1000}\)。
给定长度为 \(n\) 的单调递增正整数序列，给定一个数 \(k\)。
对 \(S\) 进行 \(k\) 次删除操作，每次以序列为下标删除最小元素，即每次同时删除集合中第 \(a_1,a_2,\dots,a_n\) 小的元素。
求 \(k\) 次删除操作后 \(S\) 中最小元素。
思路
考虑二分答案。
对于一个数 \(x\)，假设删除了 \(y\) 个小于 \(x\) 的数，那么数 \(x\) 的新排名变成 \(x-y\)。
那么我们就枚举 \(k\) 次。对于每一次操作，我们找到最后一个小于等于 \(x\) 的数 \(a_i\) 的下标 \(y\)，那么 \(x\) 的新排名就变成了 \(x-y\)。
对于一个数 \(x\)，如果它是答案，那么所有小于 \(x\) 的数的排名都会被修改成 \(0\)；所有大于 \(x\) 的数的新排名都大于等于 \(1\)。
对于二分的上界，就算 \(a_1,a_2,\dots,a_n\) 是 \(1 \sim n\) 的排列，那么最多也就删掉前面 \(n \times k\) 个数，所以答案一定小于等于 \(n \times k + 1\)。
对于 \(ans\) 的初始值，我们直接设成 \(1\)，这样相当于起到了特判的作用。
Code
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
int N,K;
int a[200500],ans;
bool Check(ll x) {
int k = K;
while(k--) {
int cur = lower_bound(a + 1,a + N + 1,x) - a;
if(a[cur] > x || cur > N)
cur --;
// ↑ 找到 a 里最后一个小于等于 x 的下标 cur
x -= cur;// 删了数后它的新排名
if(x <= 0)
return 0;
}
return 1;
}
signed main() {
ios::sync_with_stdio(false);
int T = 1;
while(T--) {
cin >> N >> K;
for(int i = 1;i <= N; i++)
cin >> a[i];
int l = 1,r = N * K + 1,ans = 1;
while(l <= r) {
int mid = (l + r) >> 1;
if(Check(mid)) {
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
cout << ans << "\n";
for(int i = 1;i <= N; i++)
a[i] = 0;
}
return 0;
}