E. Binary Inversions - 题解

比赛与标签

比赛: Codeforces Round 835 (Div. 4) 标签: data structures, greedy, math 难度: *1100

题目大意喵~

主人你好呀~ 这道题是关于一个只包含0和1的二进制数组的喵。

题目给了我们一个长度为 n 的二进制数组，我们最多可以进行一次操作：选择数组中的任意一个元素，把它翻转过来（也就是 0 变成 1，1 变成 0）。

我们的任务是，在最多进行一次翻转操作后，让这个数组的 逆序对 数量达到最大！然后输出这个最大的逆序对数量就可以啦，喵~

逆序对 是指数组中一对索引 (i, j)，满足 i < j 并且 a[i] > a[j]。在二进制数组里，这就意味着 a[i] 是 1，a[j] 是 0 啦！

解题思路分析喵~

这道题看起来有点复杂，但别担心，跟着本喵的思路一步步来，很快就能搞定的说！

我们要找的是“最大”的逆序对数量，而且操作只有“最多一次”。这就给了我们一个很明确的思考方向，我们可以把所有可能的情况都考虑一遍，然后取其中最好的结果，对吧？

总共有三种情况需要考虑呐：

不进行任何操作：我们先算一下数组最初始状态下有多少个逆序对。
翻转一个 0：我们遍历数组，尝试把每一个 0 翻转成 1，看看这样做能得到多少逆序对。
翻转一个 1：同样地，我们遍历数组，尝试把每一个 1 翻转成 0，看看逆序对数量会怎么变化。

最后，我们在这三种情况产生的所有结果中，取一个最大值，就是我们的答案啦！

那么，关键问题就变成了：如何高效地计算这些情况下的逆序对数量呢？

1. 计算初始逆序对

一个逆序对就是一个 (1, 0) 的数对，其中 1 在 0 的前面。一个很简单的计算方法是：我们从左到右遍历数组，维护一个 ones_count 变量，记录到当前位置为止遇到的 1 的数量。当我们遇到一个 0 时，这个 0 就能和前面所有的 1 形成逆序对，所以我们把 ones_count 的值累加到总逆序对数量上。这样遍历一遍，就能得到初始的逆序对数量啦！

2. 计算翻转后的逆序对变化

如果我们每次翻转都重新计算一遍总数，那太慢了喵~ (O(N^2))。聪明的做法是，在初始逆序对数量的基础上，计算每次翻转带来的 变化量（delta）。

假设我们正在考虑翻转第 i 个位置的元素 a[i]。

情况A：把 a[i] = 0 翻转成 1

失去的逆序对：原来 a[i] 是个 0，它和它前面所有的 1 构成了逆序对。假设它前面有 ones_before 个 1，那么翻转后，这些逆序对就都消失了。所以，逆序对数量减少了 ones_before。
增加的逆序对：现在 a[i] 变成了 1，它会和它后面所有的 0 构成新的逆序对。假设它后面有 zeros_after 个 0，那么逆序对数量就增加了 zeros_after。
总变化：新总数 = 初始总数 - ones_before + zeros_after。

情况B：把 a[i] = 1 翻转成 0

失去的逆序对：原来 a[i] 是个 1，它和它后面所有的 0 构成了逆序对。假设它后面有 zeros_after 个 0，翻转后这些逆序对就消失了。所以，逆序对数量减少了 zeros_after。
增加的逆序对：现在 a[i] 变成了 0，它会和它前面所有的 1 构成新的逆序对。假设它前面有 ones_before 个 1，那么逆序对数量就增加了 ones_before。
总变化：新总数 = 初始总数 + ones_before - zeros_after。

3. 整合思路

为了高效计算，我们可以这样做：

先用一次遍历，计算出数组中 0 的总数 total_zeros。
再用一次遍历，计算出初始的逆序对数量 initial_inversions。这个结果是我们保底的最大值。
最后再遍历一次数组！在这次遍历中，我们同时维护 ones_before (当前位置之前1的数量) 和 zeros_before (当前位置之前0的数量)。
- 对于每个位置 i，zeros_after 可以通过 total_zeros - zeros_before (如果a[i]==1) 或 total_zeros - zeros_before - 1 (如果a[i]==0) 快速得到。
- 根据 a[i] 的值，套用上面分析的公式，计算出翻转它之后的新逆序对总数。
- 用这个新总数来更新我们的最大值 max_inversions。

这样，我们只需要几次线性的遍历就能解决问题了，非常高效的说！

代码实现喵~

下面是AC代码的实现，本喵在关键部分加上了详细的注释，帮助主人理解哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    long long total_zeros = 0;
    // 第一次遍历：读取输入并统计数组中0的总数，喵~
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] == 0) {
            total_zeros++;
        }
    }

    // 第二次遍历：计算初始状态下的逆序对数量
    long long initial_inversions = 0;
    long long ones_count = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == 1) {
            ones_count++; // 遇到1，就把它计数
        } else {
            // 遇到0，它和前面所有的1都能构成逆序对
            initial_inversions += ones_count;
        }
    }

    // 先假设最大逆序对数就是初始值
    long long max_inversions = initial_inversions;

    // 第三次遍历：尝试翻转每一个元素，并更新最大值
    long long ones_before = 0;
    long long zeros_before = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            // 情况A：尝试把这个 0 翻转成 1
            // 失去的逆序对：这个0和前面所有1组成的对，数量为 ones_before
            // 获得的逆序对：这个新1和后面所有0组成的对
            // 后面的0的数量 = 总0数 - 前面的0数 - 当前这个0(1个)
            long long zeros_after = total_zeros - zeros_before - 1;
            long long current_inversions = initial_inversions - ones_before + zeros_after;
            max_inversions = std::max(max_inversions, current_inversions);
            zeros_before++; // 更新前面0的数量
        } else { // a[i] == 1
            // 情况B：尝试把这个 1 翻转成 0
            // 失去的逆序对：这个1和后面所有0组成的对
            // 后面的0的数量 = 总0数 - 前面的0数
            long long zeros_after = total_zeros - zeros_before;
            // 获得的逆序对：这个新0和前面所有1组成的对，数量为 ones_before
            long long current_inversions = initial_inversions + ones_before - zeros_after;
            max_inversions = std::max(max_inversions, current_inversions);
            ones_before++; // 更新前面1的数量
        }
    }
    
    std::cout << max_inversions << "\n";
}

int main() {
    // 加速输入输出，让程序跑得更快一点喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: O(N) 的说。我们对数组进行了三次独立的线性遍历（统计0，计算初始逆序对，尝试翻转），每次遍历的时间复杂度都是 O(N)。所以总时间复杂度是 O(N + N + N) = O(N)，完全可以通过的喵！
空间复杂度: O(N) 的说。我们用了一个 std::vector<int> a 来存储输入的数组，所以需要 O(N) 的空间。

知识点与总结

这道题真是一道很好的练习题呢，它融合了多种思想喵~

基准与增量思想：这是解题的核心！我们没有对每一种可能都从头计算，而是先算好一个基准值（初始逆序对），然后去计算每种操作带来的“变化量”（增量/减量），这样大大简化了计算。
前缀思想：为了快速计算变化量，我们利用了“前缀和”的思想。在遍历时，我们维护 ones_before 和 zeros_before，这其实就是一种前缀统计。通过前缀信息和总信息，我们就能O(1)地推出后缀信息 (zeros_after)。
分类讨论：解题思路清晰的关键在于把问题分解成几种简单的情况（不操作、翻转0、翻转1），然后分别处理，最后汇总。
贪心策略：虽然我们遍历了所有可能的单次翻转，但本质上是在所有“只动一下”的局部最优选择中，寻找全局最优解。这可以看作是一种贪心思想的应用。

希望本喵的讲解能帮助到主人哦！以后遇到类似的问题，可以尝试想想是不是也能用“基准+增量”的方法来解决呐！加油喵~ (ฅ'ω'ฅ)

E. Binary Inversions - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析喵~ ​

1. 计算初始逆序对 ​

2. 计算翻转后的逆序对变化 ​

3. 整合思路 ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​