COGS 942. [東方S3] 比那名居天子

Problem 1	比那名居天子(tenshi.cpp/c/pas)
题目描述	在幻想乡，比那名居天子是管理着『要石』的天人。『要石』是能够引发和镇压地震的存在，当然也可以用来改变地形。因为在幻想乡引发地震，而被灵梦等人教训了之后，天子不得不使用『要石』来修复地面。幻想乡可以视为长度为N个格子的一条横轴，其中有些格子的土地由于地震被破坏(记为1)，有些格子则没有(记为0)。每次使用『要石』，可以把一段长度为L的格子全部修复完成(即将1变为0，L覆盖的范围可以超出地图)，当然L越大，使用时所花费的灵力也就越多。天子希望最多使用K次『要石』就将所有被破坏的土地全部修复完成(即将1全部变为0)，并且花费尽可能小的灵力。她想知道能够达到这个目的的L最小是多少。
输入格式	第1行：2个整数，N, K 第2行：1个 01 串，长度为 N
输出格式	第1行：1个整数，L 的最小值
输入样例	10 3 0101111011
输出样例	3
样例解释	0101111011 > 0000111011 > 00000000011 > 0000000000
数据范围	对于 60%的数据：1 ≤ N,K ≤ 5,000 对于 100%的数据：1 ≤ N,K ≤ 500,000

二分题，做了好久，错了好久。

屠龙宝刀点击就送

运行最快 (偷笑)

#include <ctype.h>

#include <cstring>

#include <cstdio>

void read(int &x)

{

    x=;bool f=;

    char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

}

int ans=,n,k,len;

char str[];

bool judge(int L)

{

    int z=;

    for(int i=;i<=len;i++)

    {

        if(str[i]=='') i+=L-,z++;

        if(z>k) return false;

//        else i++;

    }

    return true;

}

int min(int a,int b){return a>b?b:a;}

int main()

{

    freopen("tenshi.in","r",stdin);

    freopen("tenshi.out","w",stdout);

    read(n);read(k);

    scanf("%s",str+);

    len=strlen(str+);

    int l=,r=n*;

    while(l<=r)

    {

        int mid=(l+r)>>;

        if(judge(mid))

        {

            ans=mid;

            r=mid-;

        }

        else l=mid+;

    }

    printf("%d",ans);

    return ;

}

巴特西

COGS 942. [東方S3] 比那名居天子

最新文章

热门文章