Accept: 8 Submit: 18
Time Limit: 5000 mSec Memory Limit : 65536 KB
Problem Description
人在做，天在看，单纵不怂保平安
众娘皆为轮回来，敢教POI进夜战。
勿怪战列低智商，航母不是一个样？
假摔不虚有损管，大破进击是真相！
老S最近喜欢上某个搜集战舰的游戏，这个游戏中很重要的一个内容是能编排自己的战舰，通过出击完成任务来获取资源或新的战舰。大家都说老S是一个“直男”，所以他喜欢把战舰排成一条直线。目前老S正准备完成某个新的任务--“困难级丹麦海峡”，可以将地图视为1*N的一列方格（下标为1,2,...,N），老S有K列战舰，每列战舰长度为A。老S可以将自己的战舰布局在地图中的任意位置，但是两列战舰之间至少要有一个空格子，并且显然战舰是不能重叠放置的。老S通过内部人员率先知道了敌军的炮弹将会打向那些位置，老S希望使自己的舰队尽量晚的被第一次击中。请输出老S的舰队最晚将被敌方炮弹第一次击中？如果老S的舰队可以不被敌方炮弹击中则输出-1。
Input
包含多组数据
每组数据第一行有3个整数分别为N,K,A 分别表示地图长度，老S拥有的战舰数，每艘战舰的长度。（1<=N,K,A<=200000）
第二行有1个整数M，表示敌方炮弹数。 （1<=M<=N）
第三行有M个整数，Xi表示第i个敌方炮弹将击中位置Xi (1<=Xi<=N)击中位置Xi (1<=Xi<=N)
Output
仅有一个整数ANS，表示老S最晚将被哪个炮弹第一次击中
Sample Input
5 1 3
2
1 5
5 1 3
1
3
Sample Output
-1
1
Source
FOJ有奖月赛-2015年10月
思路：二分第m个炮弹，检验：这m个炮弹把n个空格分成了t段连续的空位，对于每一段长度为g的空位，设能放x艘船， 应满足：A*x + (x-1) <= g, 得： x = (g+1) / (A+1)
,其中每两艘船之间要一个空格，放x艘船至少(x-1)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std; const int N = 2e5 + 10;
int n, k, m, A;
int pos[N], r[N]; int calc(int v) {
return (v + 1) / (A + 1);
}
bool check(int p) {
int cnt = 0;
for(int i = 1; i <= p; ++i) r[i] = pos[i];
sort(r + 1, r + p + 1);
for(int i = 2; i <= p; ++i)
{
int len = r[i] - r[i - 1] - 1;
cnt += calc(len);
}
cnt += calc(r[1] - 1);
cnt += calc(n - r[p]);
if(cnt >= k) return true;
else return false;
}
int main()
{
while(~scanf("%d%d%d", &n, &k, &A))
{
scanf("%d", &m);
for(int i = 1; i <= m; ++i) scanf("%d", &pos[i]); int low = 1, high = m; while(low < high)
{
int mid = (low + high) >> 1;
if(!check(mid)) high = mid;
else low = mid + 1;
}
if(check(m))
puts("-1");
else
printf("%d\n", low);
}
return 0;
}