51 nod 1521 一维战舰（二分）

传送门

题意

分析

这是我在51nod上的第2题，下载了4个数据，得不偿失？我太菜啦

一开始wa了6个点，下数据后发现舰与舰不能相邻，再交wa，发现l和r都没设好，再wa，发现check里面[1,b[1]]的判断写错了QAQ

此题二分[1,m]，每次将[1,mid]的数排序，计算可放舰的数量，与k比较

trick

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,k,len;

int m;

int a[200200],b[200200];

int check(int loc)

{

    int cnt=0;

    for(int i=1;i<=loc;++i) b[i]=a[i];

    sort(b+1,b+1+loc);

    //for(int i=1;i<=loc;++i) printf("%d%c",b[i],i==loc?'\n':' ');

    for(int i=2;i<=loc;++i)

    {

        if(b[i]-b[i-1]-1<len) continue;

        cnt+=(b[i]-b[i-1])/(len+1);

    }

    cnt+=(b[1])/(len+1);

    if((n-b[loc])>=len) cnt+=(n-b[loc]+1)/(len+1);

    //printf("loc=%d cnt=%d\n",loc,cnt);

    return cnt>=k;

}

int main()

{

        freopen("51nod_Problem_1521_Test_15_In.txt","r",stdin);

    scanf("%d %d %d",&n,&k,&len);

    scanf("%d",&m);

    for(int i=1;i<=m;++i) scanf("%d",a+i);

    //sort(a+1,a+1+m);

    int l=1,r=m;

    while(l+1<r)

    {

        int mid=(l+r)>>1;

        if(check(mid)) l=mid+1;else r=mid;

    }

    //if(check(l)) printf("%d\n",l);else printf("%d\n",r);

    //int mid=(l+r)>>1;

    //printf("l=%d r=%d\n",l,r);

        if(check(l)==0) printf("%d\n",l);

        else if(check(r)==0) printf("%d\n",r);

        else if(r<m) printf("%d\n",r+1);

        else puts("-1");

    return 0;

}

巴特西

51 nod 1521 一维战舰（二分）

传送门

题意

分析

trick

代码

最新文章

热门文章