FZU 2203 单纵大法好（二分）-蒲公英云

FZU 2203 单纵大法好（二分）

悠悠 2022-06-14 05:56 230阅读 0赞

题目链接：
Fzu 2203

题解：
二分。
问你老S最晚将被哪个炮弹第一次击中？显然符合答案单调性。二分一下位置在check一下就可以了。

代码：

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int w,num,len;
const int N=200000+10;
int a[N]; 
int b[N];
int check(int n)
{ 
    for(int i=1;i<=n;i++)b[i]=a[i];
    sort(b+1,b+1+n);
    int cnt = 0;
    b[0] = 0;
    b[n+1] = w+1; 
    for(int i=0;i<=n;i++){
        cnt+=(b[i+1]-b[i])/(len+1); 
    }
    if(cnt >= num) return 1;
    return 0;
}
int main()
{
    while(cin>>w>>num>>len)//地图长度，战舰数，战舰长度 
    {       
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)//炮弹的位置 
        {
            scanf("%d",&a[i]);
        } 
        int l = 1, r = n;
        int mid;
        while(l<=r)
        { 
            mid = (l+r)>>1;
            if(check(mid)){ 
                l = mid+1;
            }
            else
                r = mid-1;
        }
        if(check(n))  puts("-1");
        else cout<<l<<endl;
    }
    return 0;
}