題目不難，但是。。。
首先我的想法是從1到n,left=0,right=1,然后往兩邊數(shù)顏色相同的珠子。如果用一個(gè)大小為n的數(shù)組存字符串，一個(gè)很顯然的問題就是當(dāng)left<0或者right>n-1時(shí)就要溢出。所以要用到一個(gè)取余的函數(shù)
int cycle(int a,int n)
{
return a<0?(a%n+n):(a%n);
}
但是這樣確實(shí)太麻煩了，寫的代碼也容易出錯，我終于決定重寫了。新的想法是在字符串兩邊各復(fù)制一份相同的，這樣就是大小為3×n的字符串，而循環(huán)時(shí)只需要從n到2×n-1,解決了溢出的問題。（但是我覺得這并不是一個(gè)好方法，因?yàn)槔速M(fèi)了三倍的空間）。最終的代碼是這樣的，雖然AC了，但總不是那么完美
#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;
}
posted on 2010-10-21 14:39
cometrue 閱讀(1174)
評論(0) 編輯 收藏 引用