搜集战舰的游戏

战舰的游戏"/>

搜集战舰的游戏

题意：

给定一个成直线排布的地图，和某人拥有的战舰数量，以及每艘战舰所占用的空间大小，按时间顺序给定一些炮弹轰击的位置，问怎样摆放船只，可以让船只最晚受到炮击，并输出该炮弹序号，若可以完全避开，则输出-1。

分析：

用二分法，按炮弹的落地位置将地图分为若干部分，判断每一部分能容纳的战舰数量，若可容纳的战舰数量大于等于拥有的战舰数则说明不能击中战舰，即返回-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];//pos数组存放炮弹的落地点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");elseprintf("%d\n", low);}return 0;
}