AtCoder ABC205D. Kth Excluded
原题链接
简单
算法
(二分、差分) $O(q\log n)$
- 先维护差分数组 $C$,即 $C_i = A_i - i$,表示不超过 $A_i$ 的未出现的正整数数量
- 未出现的数必然夹在 $A_{i - 1}$ 和 $A_i$ 之间
- 对于 $K$ 而言,一定存在某两个数 $C_{r - 1}$ 和 $C_r$,$C_{r - 1}$ 对应于 $A_{r - 1}$, $C_r$ 对应于 $A_r$,使得 $C_{r - 1} < K \leqslant C_r$
- 所以,二分查找数组 $C$ 即可
- 另外, 第 k 个缺失的正整数 是这题的原题
C++ 代码
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using ll = long long;
int main() {
int n, q;
cin >> n >> q;
vector<ll> a(n);
rep(i, n) cin >> a[i];
vector<ll> c(n);
rep(i, n) c[i] = a[i] - i - 1;
rep(qi, q) {
ll k;
cin >> k;
int r = lower_bound(c.begin(), c.end(), k) - c.begin();
ll ans;
if (r == 0) ans = k;
else ans = a[r - 1] + (k - c[r - 1]);
cout << ans << '\n';
}
return 0;
}