CF 803D Magazine Ad 题解

题面

正解：一道二分大水题！

a：为什么我得不到满分？

b : 评测的系统不一样啊！

a : 蛤？

 

正常情况下我们日常练习均使用的是windows系统，在windows下，string 本身是可以存储'\0'字符，'\0'字符只是char 数组的结束符。如果是一个字符一个字符赋值，string 是可以直接输出空字符的。

而在linux的情况下(比如oi或一些oj)，string 和char[]是一个德行，根本就存不了’\0',此字符也作为string 的结束符。

 

所以说：在linux下，读取换行一定要用两遍getchar(),否则:(本来应该)------->(结果)(前提是linux评测的)

#include <bits/stdc++.h>
#pragma gcc optimize(2)
using namespace std;
int k,len;
char s[2000010];
int ans;
int bo[1000010];
int nxt[1000010];
int check(int x)
{
    if(x==1) return 1;
    register int u=1+x;
    register int num=0;
    memset(bo,0,sizeof(bo));
    while(u<=len){           
        register int tmp=nxt[u];
        while(bo[tmp]&&tmp!=0){
            tmp=nxt[tmp];
        }
        if(tmp==0){
            return 0;
        }
        else{
            bo[tmp]=1;
            ++num;
            u=tmp+1 ;
            if(num>k) return 0;  
        }
        u+=x;
    }
    return 1;
}
void erfen(int l,int r)
{
    while(l!=r)
    {
        int midd=(l+r)>>1;
        if(check(midd)) r=midd;
        else l=midd+1;
    }
    ans=l;
}
int main ()
{
    cin>>k;
    k--;
    getchar();
    //getchar(); //如果用linux评测就把该注释删掉 ，保留两个getchar() 
    int num=0;
    while(1)
    {
        char ch=getchar();
        if(ch=='\n') break;
        s[++num]=ch;
    }
    len=strlen(s+1);
    int pre=0;
    for(register int i=1;i<=len;i++){
        if(s[i]==' ') s[i]='-';
        nxt[i]=pre;
        if(s[i]=='-'){
            pre=i;
        }
    }
    erfen(1,len);
    printf("%d",ans);
}