作业帮C++ACM竞赛题植树节 Time Limit:1000MS Memory Limit:32768KDescription:植树节到了,XadillaX为了重新植一些树,不得不先拔掉一些树.这些树是整齐地排成一排,用"|"表示,中间的空隙用空格" "表示,首和尾肯定是
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/30 02:21:22
C++ACM竞赛题植树节 Time Limit:1000MS Memory Limit:32768KDescription:植树节到了,XadillaX为了重新植一些树,不得不先拔掉一些树.这些树是整齐地排成一排,用"|"表示,中间的空隙用空格" "表示,首和尾肯定是
C++ACM竞赛题
植树节
Time Limit:1000MS Memory Limit:32768K
Description:
植树节到了,XadillaX为了重新植一些树,不得不先拔掉一些树.这些树是整齐地排成一排,用"|"表示,中间的空隙用空格" "表示,首和尾肯定是一棵树.一个空格代表一个单位的空格.现在让你拔掉一定数量的树,使新的队列中最大的那个空隙最大.（忽略树本身的空隙,如果两棵树是紧挨着的,那么拔掉之后的空隙也是0）如
| || | |这么个排列,如果让你拔掉两棵树,那么最大空隙是2,即
| | |或者| | |
Input:
本题有多组数据,输入到EOF结束.每组数据第一行一个正整数N(1
C++ACM竞赛题植树节 Time Limit:1000MS Memory Limit:32768KDescription:植树节到了,XadillaX为了重新植一些树,不得不先拔掉一些树.这些树是整齐地排成一排,用"|"表示,中间的空隙用空格" "表示,首和尾肯定是
#include
#include
#include
#include
using namespace std;
const int MAX=10005;
int sum[MAX];
int bin(int low,int high,int lim,int right)
{
int ret=MAX,mid,t;
while(low>1;
t=sum[right]-sum[mid-1];
if(t>=lim)
{
ret=mid;
low=mid+1;
}
else high=mid-1;
}
return ret;
}
int main()
{
char s[MAX];
int max=0,n,t,i;
while(scanf("%d",&n)!=EOF)
{
getchar();
gets(&s[1]);
sum[0]=0;
for(i=1;s[i];i++)
{
sum[i]=sum[i-1];
if(s[i]=='|')sum[i]++;
}
max=0;
for(i=1;s[i];i++)
{
t=bin(1,i-1,n+1,i);
if(t==MAX)continue;
if((i-t+1)-(sum[i]-sum[t-1])>max)
max=(i-t+1)-(sum[i]-sum[t-1]);
}
printf("%d\n",max);
}
return 0;
}