题目翻译

\(Alice\) 和 \(Bob\) 喜欢在 \(1×n\) 的表格中玩战舰游戏。游戏开始时，\(Alice\) 有 \(k\) 艘战舰，每艘战舰长度为 \(a\) ，她需要把这些战舰不重叠且不相邻地放在格子中（不允许有两艘战舰的格子存在公共边）。但她并不会告诉 \(Bob\) 她放的位置。

接下来，\(Bob\) 会用 \(m\) 颗炮弹尝试打中 \(Alice\) 的战舰，每颗炮弹会选择一个格子打击。但由于 \(Alice\) 喜欢作弊，所以她不会告诉 \(Bob\) 什么时候击中了战舰。请你帮助 \(Bob\) 判断，在第几次发射炮弹后，\(Alice\) 一定会有一艘战舰被击中。

思路详解

这道题其实普遍的方法就两种， 因为 STRADUST 大佬写了二分做法， 所以我就来写一下 STL 做法。（主要原因还是现在在学 STL , 毕竟学了什么就要用什么）（如想查看二分做法， ）

回归正题， 上文已经说了我们要用 STL 来解决这道题， 那么， 怎么解决呢？

首先， 我们考虑一个区间 \([l, r]\) 。如果我们想在这个区间里面放战舰， 那么就根据排列组合， 既然两艘舰艇不能挨在一起， 那么就考虑往每艘舰艇的左边都多占一个， 这样就可以两条战舰挨在一起了。 但这样就会出现最左边的战舰贴着左边， 所以我们需要在区间 \([l, r]\) 的左边再加一格， 来保证贴左的问题。 所以， 这个区间的最终的 \(MAX\{可放置舰艇数量\} = (r - l + 1 + 1) / a (a 如题目所示)\) 。接下来的问题就容易的多了。

我们记录一下整个的最大可放置舰艇数为 \(smax\) 。对于每次对于一个独立区间 \([l, r]\) 的轰炸， 假设轰炸位置为 \(mid\) ， 因为 \(mid\) 处不能有战舰了， 所以原来的区间 \([l, r]\) 也就变成了两个单独的能放置战舰的区间 \([l, mid - 1]\) 和 \([mid + 1, r]\) 。那么， 这次操作对 \(smax\) 的改动为 \(smax - (r - l + 1 + 1) / a + (mid - 1 - l + 1 + 1) / a + (r - mid - 1 + 1 + 1) / a\) 。这样做似乎有点难用 STL ， 那我们再将刚才涉及的那三个区间拿出来变个形： \((l - 1, r + 1), (l - 1, mid), (mid, r + 1)\) 。 变形过后的区间就很容易发现， 其实每次操作过后的区间， 都是可以用一个 set 来存储端点的。 其原因就是每个区间中间一旦发生一次操作， 这个区间就不会再存在， 只会留下两个小的区间了。那么， 就可以想到， 每次进行轰炸的时候， 都找到自己所在的区间， 也就等价为找到自己所在的区间的左端点 （在 set 中在此位置之前第一个编号小于这个位置的位置）和右端点 （同理）， 然后更改一下最多可放置舰艇数再把这个位置丢进 set 中。 如果那次操作后最多可放置舰艇数小于了 \(k\) ， 那么这次操作 \(Alice\) 就在撒谎。

代码：

#include 
#include 
#include 
using namespace std;
 
set  s1;
 
void read (int &a) {
	a = 0;
	
	char c = getchar ();
	bool bl = 0;
	
	while (c < '0' || c > '9') {
		if (c == '-') {
			bl = 1;
		}
		c = getchar ();
	}
	while (c >= '0' && c <= '9') {
		a = (a << 1) + (a << 3) + (c ^ 48);
		c = getchar ();
	}
	a = bl ? -a : a;
}
void read (long long &a) {
	a = 0;
	
	char c = getchar ();
	bool bl = 0;
	
	while (c < '0' || c > '9') {
		if (c == '-') {
			bl = 1;
		}
		c = getchar ();
	}
	while (c >= '0' && c <= '9') {
		a = (a << 1) + (a << 3) + (c ^ 48);
		c = getchar ();
	}
	a = bl ? -a : a;
}
 
int main () {
	int n, k, a;
	int m;
	int sum = 0;
	
	read (n), read (k), read (a);
        //初始区间
	s1.insert(n + 1);
	s1.insert(0);
	sum = n / a;
	read (m);
	for (int l = 1; l <= m; l ++) {
		int x;
		
		read (x);
		s1.insert(x);
		//找到所在区间
		set  :: iterator i = s1.lower_bound(x), j = s1.upper_bound(x);
		
		i --;
		sum -= (*j - *i - 1) / a;
		sum += (x - *i - 1) / a;
		sum += (*j - x - 1) / a; 
		if (sum < k) {//判断是否撒谎
			printf ("%d", l);
			
			return 0;
		}
	}
	printf ("-1");
}