算法思想

先预处理前缀和与后缀和数组，记录各位置前 / 后各组奶牛数量；然后分别枚举升序和降序的分割点，利用前缀和快速计算不同分割下的修改次数（如前 i 个为 1 组、中间为 2 组、剩余为 3 组的情况），通过优化枚举过程（仅考虑边界点）将时间复杂度降至 O (N)；最后取两种顺序的最小修改次数作为结果。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> D(N);
    for (int i = 0; i < N; ++i) {
        cin >> D[i];
    }

    // Precompute prefix sums for not 1, not 2, not 3
    vector<int> cnt1(N + 1, 0), cnt2(N + 1, 0), cnt3(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cnt1[i] = cnt1[i - 1] + (D[i - 1] != 1);
        cnt2[i] = cnt2[i - 1] + (D[i - 1] != 2);
        cnt3[i] = cnt3[i - 1] + (D[i - 1] != 3);
    }

    // Case 1: non-decreasing 1, 2, 3
    int min_inc = N; // Initialize with maximum possible changes
    // Precompute min of (cnt1[i] - cnt2[i]) for i <= j
    vector<int> min_diff_inc(N + 1);
    int current_min = 0;
    for (int j = 0; j <= N; ++j) {
        if (j == 0) {
            current_min = cnt1[0] - cnt2[0];
        } else {
            current_min = min(current_min, cnt1[j] - cnt2[j]);
        }
        min_diff_inc[j] = current_min;
    }
    for (int j = 0; j <= N; ++j) {
        int temp = min_diff_inc[j] + cnt2[j] + (cnt3[N] - cnt3[j]);
        if (temp < min_inc) {
            min_inc = temp;
        }
    }

    // Case 2: non-increasing 3, 2, 1
    int min_dec = N;
    // Precompute min of (cnt3[i] - cnt2[i]) for i <= j
    vector<int> min_diff_dec(N + 1);
    current_min = 0;
    for (int j = 0; j <= N; ++j) {
        if (j == 0) {
            current_min = cnt3[0] - cnt2[0];
        } else {
            current_min = min(current_min, cnt3[j] - cnt2[j]);
        }
        min_diff_dec[j] = current_min;
    }
    for (int j = 0; j <= N; ++j) {
        int temp = min_diff_dec[j] + cnt2[j] + (cnt1[N] - cnt1[j]);
        if (temp < min_dec) {
            min_dec = temp;
        }
    }

    // Also consider all same (1, 1, 1), (2, 2, 2), (3, 3, 3)
    int min_same = min(cnt1[N], min(cnt2[N], cnt3[N]));

    // The answer is the minimum of all cases
    int answer = min(min_inc, min(min_dec, min_same));
    cout << answer << endl;

    return 0;
}