PKU演習問メモ(11/6)

No.	問題名	問題の種類および解法	難易度
3617	Best Cow Line	貪欲法	★★★☆☆

3617 Best Cow Line

問題概要

解法

プログラミングコンテストチャレンジブックの解説参照。

ソースコード

int n;
char in[2000],ans[2001];

int main()
{
	scanf("%d",&n);
	rep(i,n)scanf(" %c",in+i);
	
	int s=0,t=n-1,j=0;
	while(s<=t)
	{
		bool l=0;
		for(int i=0;s+i<=t;i++)if(in[s+i]!=in[t-i])
		{
			l=in[s+i]<in[t-i]; break;
		}
		putchar(in[l?s++:t--]);
		if(++j%80==0)puts("");
	}
	return 0;
}