题解 | 小苯的魔法染色

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

bool judge(char s[], int k, int m) {
	int len = strlen(s), cnt = 0;
	for (int i = 0; i < len; i++) {
		if (!cnt && s[i] == 'W') {
			if (m) {
				m--;
				cnt = k - 1;
			} else {
				return false;
			}
		} else cnt = max(cnt - 1, 0);
	}
	return true; 
}

int main() {
	int n, m;
	cin >> n >> m;
	char* s = new char[n + 1];
	scanf("%s", s);
	int len = strlen(s);
	bool all_red = true;
	for (int i = 0; i < len; i++) {
		if (s[i] == 'W') {
			all_red = false;
			break;
		} 
	}
  	//需要注意的是不能写出if (all_red) {
	//                  	cout << 0 << endl;
  	//						return 1;
	//					}会报程序退出异常的错误
	if (all_red) {
		cout << 0 << endl;
	} else {
		int l = 1, r = n / m + (n % m ? 1 : 0);
		while (r > l) {
			int mid = (r - l) / 2 + l;
			if (judge(s, mid, m)) r = mid;
			else l = mid + 1;
		}
		cout << l << endl;
	}
}