codeforces 567D – One-Dimensional Battle Ships(set二分)

One-Dimensional Battle Ships

【题意】Bob和Alice在玩一个游戏，在一个长度为n的河上，Alice放了k艘长度为a的船，每艘船之间不能相交，且两艘船之间不能相邻(即1~3,4~6是不允许的)，Bob不知道船放在哪，于是他向Alice询问了m个位置是否有船，Alice都回答了没有船，问Alice是否在撒谎。如果撒谎了求出最早第几次询问能确定Alice在撒谎。

【分析】就是给出一个空白区间，依次删除m个点，问剩余的连续段能放几艘船，把删除掉的点放入set，每次删除一个点时二分查最靠近该点的被删除的点，即可确定当前段的长度，删掉这段区间能放的船数量，加上被该点分成的新的两段的能放船的数量，当能放的船小于k时，Alice撒谎了。关键是对于计算区间长度为len时能放的船的数量(我就是没想到这个)，其实很简单，就是(len+1)/(a+1);

【AC CODE】124ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 200000+10;
int a[MAXN],n,k,s,m;
set<int> vis;

inline int get_sum(int len){ return (len+1)/(s+1);}
int sloved()
{
	int cnt = get_sum(n);
	vis.insert(0),vis.insert(n+1);
	repe(i,1,m)
	{
		auto it = vis.lower_bound(a[i]);
		int ed = *it;
		if(ed == a[i]) continue;
		it--;
		int st = *it;
		int len =ed-st-1;
		vis.insert(a[i]);
		if(len < s) continue;
		cnt -= get_sum(len);
		cnt += get_sum(a[i]-st-1)+get_sum(ed-a[i]-1);
		if(cnt < k) return i;
	}
	return -1;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	scanf("%d %d %d %d", &n, &k, &s, &m);
	repe(i,1,m) scanf("%d", &a[i]);
	printf("%d\n",sloved());
	return 0;
}