人在做，天在看，单纵不怂保平安
众娘皆为轮回来，敢教POI进夜战。
勿怪战列低智商，航母不是一个样？
假摔不虚有损管，大破进击是真相！
老S最近喜欢上某个搜集战舰的游戏，这个游戏中很重要的一个内容是能编排自己的战舰，通过出击完成任务来获取资源或新的战舰。大家都说老S是一个“直男”，所以他喜欢把战舰排成一条直线。目前老S正准备完成某个新的任务--“困难级丹麦海峡”，可以将地图视为1*N的一列方格（下标为1,2,...,N），老S有K列战舰，每列战舰长度为A。老S可以将自己的战舰布局在地图中的任意位置，但是两列战舰之间至少要有一个空格子，并且显然战舰是不能重叠放置的。老S通过内部人员率先知道了敌军的炮弹将会打向那些位置，老S希望使自己的舰队尽量晚的被第一次击中。请输出老S的舰队最晚将被敌方炮弹第一次击中？如果老S的舰队可以不被敌方炮弹击中则输出-1。
包含多组数据
每组数据第一行有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)
仅有一个整数ANS，表示老S最晚将被哪个炮弹第一次击中
解题思路：二分炮弹个数
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <climits> #include <functional> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int a[200010],b[200010]; int k,n,len,m; bool check(int x) { for(int i=1;i<=x;i++) b[i]=a[i]; sort(b+1,b+x+1); b[0]=0; b[x+1]=n+1; int sum=0; for(int i=1;i<=x+1;i++) sum+=(b[i]-b[i-1])/(len+1); if(sum>=k) return true; else return false; } int main() { while(~scanf("%d %d %d",&n,&k,&len)) { scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&a[i]); int l=1,r=m,ans=0; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) { ans=mid; l=mid+1; } else r=mid-1; } if(check(m)) printf("-1\n"); else printf("%d\n",ans+1); } return 0; }