D. Stay or Mirror - 题解

比赛与标签

比赛: Codeforces Round 1040 (Div. 2) 标签: greedy

题目大意喵~

主人你好呀~ 这道题是这样的喵~ (ฅ'ω'ฅ)

我们拿到一个长度为 n 的排列 p（也就是 1 到 n 这 n 个数，顺序打乱了而已）。 我们需要构造一个新的数组 a，长度也是 n。对于 p 里面的每一个数字 p_i，我们有两种选择来决定 a_i 的值：

1. 保持不变：a_i = p_i
2. 镜像变换：a_i = 2n - p_i

我们的任务就是，为每一个 p_i 做出最喵的选择，使得最终构造出的数组 a 的逆序对数量最少。

一个逆序对指的是数组中一对下标 (i, j)，满足 i < j 并且 a_i > a_j。

简单来说，就是通过二选一的操作，让新数组尽可能地有序，喵~

解题思路喵~

这道题看起来每个位置都有两种选择，2^n 种可能性，直接暴力肯定是不行的说。标签提示我们是贪心，那么我们来找找看有没有什么漂亮的贪心性质吧，喵~

1. 初步分析与基准情况

首先，咱们可以先算一个基准值。如果我们对所有的 p_i 都不做任何改变，也就是 a = p，这时候的逆序对数量是多少呢？这个很容易用 O(n^2) 的双重循环算出来，我们叫它 base_inversions 好了。

2. “小值”与“大值”的发现

接下来是关键的一步！我们观察一下两种选择 p_i 和 2n - p_i 的范围。

• p_i 是排列里的数，所以 1 <= p_i <= n。我们叫它“小值”吧。
• 2n - p_i 呢？因为 1 <= p_i <= n，所以 n <= 2n - p_i <= 2n - 1。我们叫它“大值”好了。

看到了吗喵？任何一个“小值”都小于等于任何一个“大值”！(最特殊的情况是当 p_i = n 时，p_i 和 2n - p_i 都是 n)。

这个发现非常重要！它能大大简化我们对逆序对的分析：

• 如果 a_i 是“大值”，a_j 是“小值”，且 i < j，那么 a_i > a_j 必然成立，这就一定会产生一个逆序对。
• 如果 a_i 是“小值”，a_j 是“大值”，且 i < j，那么 a_i < a_j 必然成立，就一定不会产生逆序对。

3. 独立决策的奇迹

现在我们来考虑，对一个 p_i，我们把它从“小值”p_i 翻转成“大值”2n - p_i，逆序对数量会怎么变化呢？

最直观的想法是，这个变化量 delta_i 取决于其他的 a_j 是“小值”还是“大值”，这样决策之间就相互依赖了，没法贪心呀！QAQ

但是！奇迹发生了！我们可以通过一点点数学推导，证明每个位置的决策是独立的！

我们设 c_i 是一个选择变量，c_i = 0 表示我们选择 a_i = p_i（小值），c_i = 1 表示我们选择 a_i = 2n - p_i（大值）。

最终总的逆序对数量可以表示成一个关于所有 c_i 的函数。经过一番魔法般的推导（其实就是把所有情况的逆序对贡献加起来化简），我们可以得到一个超级优美的公式：

总逆序对 = base_inversions + Σ ( c_i * delta_i )

这里的 base_inversions 就是我们一开始算的全是“小值”时的逆序对数。而 delta_i 是一个只和 p_i 与它在原数组 p 中的前后元素大小关系有关的常数！

delta_i 的含义是：假设其他元素都不变（都是小值），只将 p_i 翻转成 2n - p_i，逆序对数量的变化量。

我们来算一下这个 delta_i：

• 原来 p_i 与 j < i 的 p_j 产生的逆序对，是 p_j > p_i 的 p_j 的数量。我们记作 count_before_greater。
• 原来 p_i 与 j > i 的 p_j 产生的逆序对，是 p_i > p_j 的 p_j 的数量。
• 当 p_i 变为 2n - p_i（大值）后：
  • 对于 j < i，p_j 是小值，2n - p_i 是大值，所以 p_j < 2n - p_i，逆序对为0。
  • 对于 j > i，p_j 是小值，2n - p_i 是大值，所以 2n - p_i > p_j，总是会产生逆序对。这样的 j 有 n - 1 - i 个。

所以，变化量 delta_i = (翻转后的逆序对) - (翻转前的逆序对) delta_i = (n - 1 - i) - (count_before_greater + count_after_smaller)

这里 count_after_smaller 是 j > i 且 p_j < p_i 的数量。 我们知道 (count_after_smaller + count_after_greater) = n - 1 - i。 所以 count_after_smaller = n - 1 - i - count_after_greater。 代入一下，delta_i = (n - 1 - i) - (count_before_greater + n - 1 - i - count_after_greater)delta_i = count_after_greater - count_before_greater

这里的 count_after_greater 是指在 p 数组中，i 之后比 p_i 大的数的个数。count_before_greater 是 i 之前比 p_i 大的数的个数。

4. 贪心策略

既然总逆序对 I = base_inversions + Σ (c_i * delta_i)，为了让 I 最小，我们就要让 Σ (c_i * delta_i) 最小。

因为每个 c_i 的选择（0或1）只影响 c_i * delta_i 这一项，所以我们可以对每个 i 独立做决策啦！

• 如果 delta_i < 0，说明翻转能减少逆序对，我们当然要翻转！选择 c_i = 1，总变化量就加上这个负的 delta_i。
• 如果 delta_i >= 0，说明翻转不会变得更好（甚至可能变差），那我们就不翻转啦。选择 c_i = 0，总变化量加 0。

所以，最终的算法就是：

1. 计算 base_inversions。
2. 对每个 i 从 0 到 n-1： a. 计算 delta_i = count_after_greater - count_before_greater。 b. 如果 delta_i < 0，就把这个 delta_i 加到一个累加器 total_delta 里。
3. 最终答案就是 base_inversions + total_delta。

这个算法的复杂度是 O(n^2)，对于 n 最大 5000 且总和不超过 5000 的情况，是完全可以接受的！

代码实现喵~

#include <iostream> 
#include <vector> 
#include <numeric> 
#include <algorithm> 
 
void solve() { 
    int n; 
    std::cin >> n; 
    std::vector<int> p(n); 
    for (int i = 0; i < n; ++i) { 
        std::cin >> p[i]; 
    } 
 
    // 步骤1：计算如果我们什么都不做 (a=p) 时的基础逆序对数量，喵~
    long long base_inversions = 0; 
    for (int i = 0; i < n; ++i) { 
        for (int j = i + 1; j < n; ++j) { 
            if (p[i] > p[j]) { 
                base_inversions++; 
            } 
        } 
    } 
 
    // 步骤2：对每个位置i，计算把它翻转带来的“收益”，如果收益是负的（即逆序对减少），就采纳它
    long long total_delta = 0; 
    for (int i = 0; i < n; ++i) { 
        int current_val = p[i]; 
 
        // 计算在 p[i] 之后，有多少个元素比 p[i] 大
        int count_after_greater = 0; 
        for (int j = i + 1; j < n; ++j) { 
            if (p[j] > current_val) { 
                count_after_greater++; 
            } 
        } 
 
        // 计算在 p[i] 之前，有多少个元素比 p[i] 大
        int count_before_greater = 0; 
        for (int k = 0; k < i; ++k) { 
            if (p[k] > current_val) { 
                count_before_greater++; 
            } 
        } 
 
        // 这就是我们推导出的变化量 delta_i
        long long delta = (long long)count_after_greater - count_before_greater; 
 
        // 如果变化量是负数，说明翻转 p[i] 是个好主意，我们把它计入总变化量
        if (delta < 0) { 
            total_delta += delta; 
        } 
    } 
 
    // 最终答案 = 基础逆序对 + 所有负的delta之和
    std::cout << base_inversions + total_delta << " \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^2) 的说。计算 base_inversions 需要两层循环，是 O(n^2)。接着计算所有 delta_i，对于每个 i，我们又需要遍历它前面和后面的元素，这部分总共也是 O(n^2)。所以总时间复杂度是 O(n^2)。
• 空间复杂度: O(n) 的说。我们只需要一个数组 p 来存储输入的排列，所以空间复杂度是 O(n)。

知识点与总结喵~

这道题真是一道非常巧妙的贪心题呢！(๑•̀ㅂ•́)و✧

1. 核心思想: 关键在于将一个复杂的、决策互相依赖的问题，通过数学变换，转化为了一个每个决策都相互独立的问题。I = base_inversions + Σ (c_i * delta_i) 这个公式就是解题的钥匙！
2. 边界分析: 对 p_i 和 2n - p_i 的值域进行分析，得出“小值”和“大值”的结论，是简化问题的突破口。很多时候，注意题目给定的数值范围会带来意想不到的收获哦。
3. 贪心证明: 虽然我们是贪心地选择了所有 delta_i < 0 的情况，但背后是有严格的数学公式保证其正确性的。这告诉我们，一个好的贪心策略往往不是凭感觉，而是能够被证明的。
4. 编程技巧: 对于这类问题，先计算一个基准值，再计算每个独立操作带来的变化量，是一种常见的解题模式。

希望这篇题解能帮助到主人哦！下次遇到难题也别怕，静下心来，说不定就能发现其中的小秘密啦~ 喵~