随笔-6  评论-2  文章-0  trackbacks-0

#include <stdio.h>
#include 
<stdlib.h>
int main()
{
    FILE 
*fin,*fout;
    fin
=fopen("beads.in","r");
    fout
=fopen("beads.out","w");
    
char *beads;
    
int n;
    fscanf(fin,
"%d",&n);
    beads
=(char *)malloc(3*n*sizeof(char));
    fscanf(fin,
"%s",beads);
    
int i,a,b,left,right,sum=0;
    
for(i=n;i<3*n;++i)
    {
        beads[i]
=beads[i-n];
    }
    
for(i=n;i<2*n;++i)
    {
        left
=i;
        right
=i+1;
        
char ch;

        
while(beads[left]=='w'&&left>=0)--left;
        ch
=beads[left];
        
while(left>0&&(beads[left-1]==ch||beads[left-1]=='w'))--left;
        a
=i-left+1;

        
while(beads[right]=='w'&&right<3*n)++right;
        ch
=beads[right];
        
while(right<(3*n-1)&&(beads[right+1]==ch||beads[right+1]=='w'))++right;
        b
=right-i;

        
if(a+b>sum)sum=a+b;
        
if(a>=n||b>=n||a+b>n)sum=n;
    }
    fprintf(fout,
"%d\n",sum);
    
return 0;
}
首先我的想法是从1到n,left=0,right=1,然后往两边数颜色相同的珠子。如果用一个大小为n的数组存字符串,一个很显然的问题就是当left<0或者right>n-1时就要溢出。所以要用到一个取余的函数。
但是这样确实太麻烦了,写的代码也容易出错,我终于决定重写了。新的想法是在字符串两边各复制一份相同的,这样就是大小为3×n的字符串,而循环时只需要从n到2×n-1,解决了溢出的问题。(但是我觉得这并不是一个好方法,因为浪费了三倍的空间)。最终的代码是这样的,虽然AC了,但总不是那么完美。













posted on 2010-10-21 14:54 cometrue 阅读(1249) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理