Java实现蓝桥杯VIP 算法提高项链

算法提高项链

时间限制：1.0s 内存限制：512.0MB

问题描述

　　由 n(1≤n≤100)　　个珠子组成的一个项链，珠子有红、蓝、白三种颜色，各种颜色的珠子的安排顺序由键盘输入的字符串任意给定。蓝色用小写字母b表示,红色用小写字母r表示,　　白色用小写字母w表示.

假定从项链的某处将其剪断，把它摆成一条直线。先从左端向右收集同色珠子，遇到第一个异色珠子时停止.　　收集过程中, 白色是一种特殊颜色, 既可以看成红色也可以看成蓝色。然后再从剩余珠子的右端向左重复上述过程。

例如：对下图一所示的项链, 如果从图一中标记的位置0处剪断,　　则按顺时针顺序得到wbbbwwrrbwbrrwb（如图二所示）。这时从左端开始收集可以得到wbbbww,　　共6个珠子；然后从剩余珠子右端开始收集得到wb，共2个珠子。这种剪法共可收集到6+2=8个珠子。如果从图一中标记的位置4处剪断,　　则按顺时针顺序得到wwrrbwbrrwbwbbb（如图二所示）。这时从左端收集可以得到wwrr,共4个珠子；然后从剩余珠子右端收集可以得到wbwbbb，共6个珠子。这种剪法共可收集到4+6=10个珠子。

要求: 在项链中选择合适的剪断位置, 使得从左右两端收集到的珠子数目之和最大，输出收集到的珠子数的最大值M。

输入格式

　　由小写字母b,r,w组成的字符串。此字符串记录了一个首尾相接的项链从某处断开后，按顺时针顺序得到的珠子的直线排列。

输出格式

　　收集到的珠子数的最大值 M

样例输入

wbbbwwrrbwbrrwb

样例输出

import java.util.Scanner;

public class 项链 {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		String string = scanner.nextLine();

		int ma = 0;

		for (int i = 0; i < string.length(); i++) {

			int mm = get(string, i);

			ma = mm > ma ? mm : ma;

		}

		System.out.println(ma);

	}

	private static int get(String string, int i) {

		String s1 = string.substring(i) + string.substring(0, i);

		int j1 = 0;

		int j2 = 0;

		char c1 = 'w';

		char c2 = 'w';

		for (int k = 0; k < s1.length(); k++) {

			if (s1.charAt(k) != c1) {

				c1 = s1.charAt(k);

				break;

			}

		}

		for (int k = s1.length() - 1; k > 0; k--) {

			if (s1.charAt(k) != c2) {

				c2 = s1.charAt(k);

				break;

			}

		}

		for (int j = 0; j < s1.length(); j++) {

			if (s1.charAt(j) == c1 || s1.charAt(j) == 'w')

				j1++;

			else {

				break;

			}

		}

		for (int j = s1.length() - 1; j >0; j--) {

			if (s1.charAt(j) == c2 || s1.charAt(j) == 'w')

				j2++;

			else {

				break;

			}

		}

		if (j1 == s1.length())

			return j1;

		return j1 + j2;

	}

}

巴特西

Java实现蓝桥杯VIP 算法提高项链

最新文章

热门文章

巴特西

Java实现 蓝桥杯VIP 算法提高 项链

最新文章

热门文章

Java实现蓝桥杯VIP 算法提高项链