Translate:USACO/beadsBroken Necklace 坏掉的项链
[编辑]题目描述你有一条由N个红色的,白色的,或蓝色的珠子组成的项链(3<=N<=350),珠子是随意安排的。 这里是 n=29 的二个例子: 1 2 1 2 r b b r b r r b r b b b r r b r r r w r b r w w b b r r b b b b b b r b r r b r b r r r b r r r r r r b r b r r r w 图片 A 图片 B r 代表 红色的珠子 b 代表 蓝色的珠子 w 代表 白色的珠子 第一和第二个珠子在图片中已经被作记号。 brbrrrbbbrrrrrbrrbbrbbbbrrrrb 假如你要在一些点打破项链,展开成一条直线,然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子,在另一端做同样的事(颜色可能与在这之前收集的不同)。 确定应该在哪里打破项链来收集到最大数目的珠子。 白色珠子什么意思?在一些项链中还包括白色的珠子(如图片B) 所示。 [编辑]程序名称beads [编辑]输入格式第 1 行: N, 珠子的数目 [编辑]样例输入(文件 beads.in) 29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb [编辑]输出格式单独的一行 最大可能取得的珠子数 [编辑]样例输出(文件 beads.out) 11 /*
ID: liluvu1
LANG: C++
TASK: beads
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 350
char beads[MAXLEN];
int main(){
FILE *fin = NULL;
FILE *fout = NULL;
fin = fopen("beads.in", "r");
fout = fopen("beads.out", "w");
int n = 0;
fscanf(fin, "%d\n", &n);
for (int i = 0; i < n; i++)
fscanf(fin, "%c", &beads[i]);
int l = 0;
int r = 0;
int nw = 0;
int max = 0;
for (int i = 0; i < n; i++){
int vl = 0;
int vr = 0;
r = i;
l = (i-1+n)%n;
// right direction
while (beads[r] == 'w') {
vr++;
r = (r+1)%n;
if (r == i) {
fprintf(fout, "%d\n", vr);
return 0;
}
}
nw = beads[r]; // first not w
vr++; // count it
r = (r+1)%n;
while ((r != i) && (nw == beads[r] || beads[r] == 'w')){
vr++;
r = (r+1)%n;
}
if (r != i) {
// left direction
while (beads[l] == 'w'){
vl++;
l = (l-1+n)%n;
}
nw = beads[l]; //first not w
vl++;
l = (l-1+n)%n;
r = (r-1+n)%n;
while ((l != r) && (nw == beads[l] || beads[l] == 'w')){
vl++;
l = (l-1+n)%n;
}
} else {
fprintf(fout, "%d\n", vr);
return 0;
}
// printf("i = %d, %d, %d\n", i, vr, vl);
if (vl+vr > max){
max = vl+vr;
}
}
fprintf(fout, "%d\n", max);
return 0;
} |
|