代码：《挑战程序设计竞赛》3.2.2
#include<iostream> using namespace std; #define MAX_N 10000 int N; //牛的个数 int f[MAX_N]; //用于判断区间[i, i + 1 - K]是否进行了反转，区间[i, i + K - 1]进行了反转，f[i]=1，否则为0 int dir[MAX_N]; //牛的方向，0是前，1是后 /*核心思想：如果从标号为i-K+1到i-1的牛的反转次数之和为奇数，则第i头牛的方向与起始方向相同，否则相反，并用sum记录这个值 而标号为i的牛的sum值 = 标号为i-1的牛的sum值 + 标号i的牛的反转次数 - 标号i-K+1的牛的反转次数*/ int calc(int K) //对于固定的K，计算是否有可行解,即对应的最小操作次数 { memset(f, 0, sizeof(f)); int res = 0; //反转次数 int sum = 0; //f的和，用于记录标号为i的牛之前的反转次数 for (int i = 0; i + K <= N; i++) { if ((dir[i] + sum) % 2 != 0) //最左端的牛（标号为i的牛）面向后方（判断方法：标号为i的牛的最初的方向加上该头牛在之前的反转次数，如果为偶数，现在面向的前方，否则为后方） { res++; //反转次数加1 f[i] = 1; //区间[i, i + K - 1]标记为进行了反转 } sum += f[i]; //sum加上区间[i, i + K - 1]的反转次数 if (i - K + 1 >= 0) //如果标号为i的牛位于区间[0, K-1)之后 { sum -= f[i - K + 1]; //sum减去区间[i - K + 1, i]的反转次数，计算标号为i+1的牛的反转次数时不能将其纳入 } } //检查剩余的牛是否有面朝后方的情况 for (int i = N - K + 1; i < N; i++) { if ((dir[i] + sum) % 2 != 0) return -1; //无解 if (i - K + 1 >= 0) //如果标号为i的牛位于区间[0, K-1)之后 { sum -= f[i - K + 1]; //sum减去区间[i - K + 1, i]的反转次数 } } return res; } void solve() { int K = 1, M = N; for (int k = 1; k <= N; k++) { int m = calc(k); if (m >= 0 && M > m) { M = m; K = k; } } cout <<"K = " << K << " " << "M = " << M << endl; } int main() { char direction; cin >> N; for (int i = 0; i < N; i++) { cin >> direction; if (direction == 'B') dir[i] = 1; else dir[i] = 0; } solve(); return 0; } //测试用例 /* 7 BBFBFBB */