首页 > USACO题解 > USACO Broken Necklace

USACO Broken Necklace

我的解题思路就是把两个串连接起来,这样好看成是一个环。特殊情况特殊考虑:字符串中没有r那么返回n,字符串中没有b那么也返回n。

接下来处理正常情况,首先不考虑前导的w,因为我们在后面会计算到。然后依次处理字母,找出r的最大长度、b的最大长度(如果当前字符与下一个字符不相等且都不是w,那么当前字符和下一个字符中间肯定可以分开。从中求出r和b的长度和)。如果当前字符是b下一个字符是r,则将r的长度重置为0;反之b的长度重置为0.如果当前字符是w则回退。

需要注意的地方:

rrrwwwwbbb中w不要算两次;rrrwwwwbbb的最大长度为n,如果是采用两个串连接,算出来可能大于n,那么你要返回n。

感觉我的思路表达起来不是很清楚@@代码也很冗长

/*
	ID:stackex1
	LANG:C
	PROG:beads
*/
#include <stdio.h>
#include <string.h>

#define MAX_LEN 1024

char str[MAX_LEN], tmp[MAX_LEN];

int work()
{
	int i, j, l, bl, rl, res;
	int bidx, ridx, widx;
	l = strlen(str);
	/*字符串中没有b*/
	i = 0;
	while(i < l && str[i] != 'b') ++i;
	if(i == l) return (l >> 1);
	/*字符串中没有r*/
	i = 0;
	while(i < l && str[i] != 'r') ++i;
	if(i == l) return (l >> 1);
	/*去除前导的字符w*/
	i = 0;
	while(str[i] == 'w') ++i;
	/*开始计算长度*/
	bl = rl = res = j = 0;
	bidx = ridx = widx = 0;
	while(i < l)
	{
		switch(str[i])
		{
		case 'r':
			while(i < l && (str[i] == 'r' || str[i] == 'w'))
			{
				if(str[i] == 'r') ridx = i;
				++i;
				++rl;
			}
			rl += j;
			break;
		case 'b':
			while(i < l && (str[i] == 'b' || str[i] == 'w'))
			{
				if(str[i] == 'b') bidx = i;
				++i;
				++bl;
			}
			bl += j;
			break;
		default:
			break;
		}
		if((widx - ridx)*(widx - bidx) < 0)
		{
			if(res < bl + rl - j) res = bl + rl - j;
		}
		else
		{
			if(res < bl + rl) res = bl + rl;
		}
		j = 0;
		/*如果当前字符是b*/
		if(str[i] == 'b') bl = 0;
		/*如果当前字符是r*/
		else if(str[i] == 'r') rl = 0;
		/*如果前一个是w则回溯*/
		if(str[i - 1] == 'w')
		{
			j = i;
			--i;
			while(str[i] == 'w') --i;
			++i;
			widx = i;
			j -= i;
			i += j;
		}
	}
	return res > l/2 ? l/2 : res;
}

int main(int argc, char **argv)
{
	int n, i;
	
	FILE *fin = fopen("beads.in", "r");
	FILE *fout = fopen("beads.out", "w");
	
	fscanf(fin, "%d%*c", &n);
	fscanf(fin, "%s", tmp);
	
	memset(str, 0, sizeof(str));
	strcat(str, tmp);
	strcat(str, tmp);
	
	fprintf(fout, "%d\n", work());
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO Broken Necklace
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: USACO题解 标签: ,
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.