[USACO08FEB] Dining Cows B

GitHub跳转原题关系图返回列表

枚举分界点，统计前缀里需要改成 1 的 2 的数量和后缀里需要改成 2 的 1 的数量，取最小值。

OJ: luogu

题目 ID: P2837

难度:普及-

标签:前缀和枚举

日期: 2026-06-19 11:22

目录

  1. 题意
  2. 思路
    1. 核心公式
  3. 代码
  4. 复杂度
  5. 总结

题意

给出一个只由 1 和 2 组成的队伍。

你不能移动奶牛，只能修改某些位置上的编号。

目标是让最终队伍变成：

  • 前面一段全是 1
  • 后面一段全是 2

其中任意一段都可以为空，所以“全是 1”或者“全是 2”也都算合法。

要求最少修改多少个位置。

思路

最终队伍一定可以看成某个分界点 cut：

  • 1..cut 这一段应该全是 1
  • cut+1..n 这一段应该全是 2

最直接的办法就是枚举这个分界点。

先看一个按定义直接统计代价的朴素解：

cpp
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：枚举分界点并暴力统计左右两边的错误数量。

const int MAXN = 30005;

int n;
int a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int ans = n;

    for (int cut = 0; cut <= n; cut++) {
        int cost = 0;

        for (int i = 1; i <= cut; i++) {
            if (a[i] != 1) {
                cost++;
            }
        }

        for (int i = cut + 1; i <= n; i++) {
            if (a[i] != 2) {
                cost++;
            }
        }

        ans = min(ans, cost);
    }

    cout << ans << '\n';
    return 0;
}

对于固定的 cut：

  • 左边前缀里所有的 2 都要改成 1
  • 右边后缀里所有的 1 都要改成 2

所以代价就是：

前缀里 2 的个数 + 后缀里 1 的个数

brute.cpp 的问题在于：每换一个分界点，都要重新扫描左右两边，复杂度是 O(n2)O(n^2)。

这里可以用前缀和优化。

设：

  • pre_two[i] 表示前 i 个位置里 2 的数量
  • pre_one[i] 表示前 i 个位置里 1 的数量

那么枚举分界点 cut 时：

  • 左边要改的数量是 pre_two[cut]
  • 右边要改的数量是 pre_one[n] - pre_one[cut]

总修改次数就是：

pre_two[cut] + pre_one[n] - pre_one[cut]

把 cut = 0..n 全部枚举一遍，取最小值即可。

其中：

  • cut = 0 表示整条队伍都变成 2
  • cut = n 表示整条队伍都变成 1

核心公式

设 preOneipreOne_i 表示前 ii 个位置里 11 的数量，preTwoipreTwo_i 表示前 ii 个位置里 22 的数量。枚举分界点 cutcut，代价为：

cost(cut)=preTwocut+(preOnen−preOnecut) cost(cut)=preTwo_{cut}+(preOne_n-preOne_{cut})

其中左边的 22 要改成 11，右边的 11 要改成 22。最终答案是：

min⁡0⩽cut⩽ncost(cut) \min_{0\leqslant cut\leqslant n} cost(cut)

公式解释：分界点左边最终都应该是 1，所以左边出现的 2 都要修改；右边最终都应该是 2，所以右边出现的 1 都要修改。前缀和让这两个数量可以 O(1)O(1) 算出。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30005;

int n;
int a[MAXN];
int pre_one[MAXN];
int pre_two[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre_one[i] = pre_one[i - 1] + (a[i] == 1);
        pre_two[i] = pre_two[i - 1] + (a[i] == 2);
    }

    int ans = n;

    // 枚举分界点 cut：
    // [1..cut] 最终都应该是 1，
    // [cut+1..n] 最终都应该是 2。
    for (int cut = 0; cut <= n; cut++) {
        int change_left = pre_two[cut];
        int change_right = pre_one[n] - pre_one[cut];
        ans = min(ans, change_left + change_right);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

总结

这题的关键不是“怎么改”，而是先看清最终形态一定只有一个分界点。

一旦把问题转成“枚举分界点”，答案就能拆成“左边错了多少个 2”和“右边错了多少个 1”，用前缀和就能在线性时间内做完。