3515704_ac_4172ms_4596k.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 55 行

import java.util.*;

public class Main {
	private Scanner in;
	private int N;
	private byte [] pos;

	public static void main(String [] args) {
		new Main().run();
	}

	private void run() {
		Scanner in = new Scanner (System.in);
		String p, q = "F";

		N = in.nextInt();
		pos = new byte [N + 1];
		for (int i = 0; i < N; i++) {
			p = in.next();
			if (!p.equals(q)) {
				q = p;
				pos[i] = 1;
			}
		}
		if ("B".equals(q)) {
			pos[N] = 1;
		}
		int ansm, ansk;
		ansm = ansk = N + 1;
		for (int i = 1; i <= N; i++) {
			int need = solve(i);
			if (need < ansm) {
				ansm = need;
				ansk = i;
			}
		}
		System.out.println(ansk + " " + ansm);
	}

	private int solve(int k) {
		int ret = 0, i;
		byte [] tmp = new byte [N + 1];
		System.arraycopy(pos, 0, tmp, 0, tmp.length - 1);
		for (i = 0; i <= N - k; i++) {
			ret += tmp[i];
			tmp[i + k] ^= tmp[i];
		}
		while (i < N) {
			if (tmp[i++] == 1) {
				return N + 1;
			}
		}
		return ret;
	}
}