老题解批量补档。
https://www.luogu.com.cn/problem/CF567D
因为「某一时刻是否一定被击中过」具有单调性，考虑先提前发射所有炮弹，倒序枚举炮弹，不断「撤销」当前最后一发炮弹的发射，如果在「撤销」这发炮弹后，存在任意一种放下 \(k\) 艘完整的战舰的方案，说明在发射这一发炮弹之后绝对能够击中。
如果发射所有炮弹后，依然存在一种放下 \(k\) 艘完整的战舰的方案，则无解。
具体实现可以使用并查集维护连通块大小，每「撤销」一发炮弹的发射相当于合并三个连通块：炮弹的落点、落点的前一个元素（若不存在或已被炮弹摧毁则忽略）、落点的后一个元素（若不存在或已被炮弹摧毁则忽略）。
设某连通块大小为 \(x\)，可容纳战舰数为 \(res\)，显然有 \(res = \lfloor (x + 1) \div (p + 1) \rfloor\)。
记统计当前可容纳战舰的数量为 \(ans\)，在并查集合并时，\(ans\) 分别减去两个待合并连通块的可容纳战舰的数量，再加上新连通块可容纳战舰的数量。最靠后的 \(ans\ge k\) 的时刻即为所求。
同时使用路径压缩和按秩合并，时空复杂度均为 \(\mathcal O(n)\)。优于 multiset 解法。
namespace XSC062 {
using namespace fastIO;
const int maxn = 2e5 + 15;
bool vis[maxn];
int n, k, p, m, x, ans;
int a[maxn], f[maxn], siz[maxn];
inline void swap(int &x, int &y){
x ^= y ^= x ^= y;
return 0;
}
inline int calc(int x) {
return (x + 1) / (p + 1);
}
inline void Init(int n) {
for (int i = 1; i <= n; ++i) {
f[i] = i;
siz[i] = 1;
}
return;
}
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
inline void merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx == fy)
return;
ans -= calc(siz[fx]);
ans -= calc(siz[fy]);
if (siz[fy] > siz[fx])
swap(fx, fy);
ans += calc(siz[fy]);
f[fx] = fy;
return;
}
int main() {
read(n);
read(k);
read(p);
read(m);
Init(n + 5);
ans = (n - m) * (2 / (p + 1));
for (int i = 1; i <= m; ++i) {
read(a[i]);
vis[a[i]] = 1;
}
for (int i = 1; i <= n; ++i) {
if (vis[i] || vis[i - 1])
continue;
merge(i, i - 1);
}
if (ans >= k) {
puts("-1");
return 0;
}
for (int i = m; i; --i) {
vis[a[i]] = 0;
ans += 2 / (p + 1);
if (a[i] - 1 && !vis[a[i] - 1])
merge(a[i], a[i] - 1);
if (a[i] + 1 <= n && !vis[a[i] + 1])
merge(a[i], a[i] + 1);
if (ans >= k) {
printf("%d", i);
return 0;
}
}
puts("-1");
return 0;
}
} // namespace XSC062
int main() {
XSC062::main();
return 0;
}