欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CF 803D Magazine Ad 题解

程序员文章站 2022-07-05 08:27:45
题面 正解:一道二分大水题! A:为什么我得不到满分? B : 评测的系统不一样啊! A : 蛤? 正常情况下我们日常练习均使用的是windows系统,在windows下,string 本身是可以存储'\0'字符,'\0'字符只是char 数组的结束符。如果是一个字符一个字符赋值,string 是可 ......

题面

正解:一道二分大水题!

a:为什么我得不到满分?

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

a : 蛤?

 

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

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

 

所以说:在linux下,读取换行一定要用两遍getchar(),否则:CF 803D Magazine Ad 题解(本来应该)------->CF 803D Magazine Ad 题解(结果)(前提是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);
}