Moe's CF Life

喵~ 各位算法大师们好呀！我是你们的小助教猫娘，今天也要元气满满地解决问题哦！(ฅ´ω`ฅ)

今天我们要看的题目是 Penchick and Modern Monument，一个关于排列柱子的小问题。别看它好像很复杂，其实只要找到其中的小窍门，一下子就能想通啦！

题目大意

让本猫娘来给你简单描述一下问题吧，喵~

在一个叫做 Metro Manila 的大城市里，有个叫 Penchick 的建筑经理建了一座有 n 根柱子的纪念碑。这些柱子的高度本来应该是非递减的（也就是 h[i] <= h[i+1]，像上楼梯一样），结果工人师傅不小心把它们建成了非递增的（h[i] >= h[i+1]，像下楼梯一样）。

幸运的是，Penchick 可以施展魔法！他可以进行一种操作：

选择任意一根柱子 i，把它变成任意一个正整数高度 x。

现在的问题是，为了让柱子的高度序列变回非递减的，Penchick 最少需要施展多少次魔法呢？

举个例子：如果柱子是 [5, 4, 3, 2, 1]，我们可以把它变成 [2, 2, 3, 4, 4]。我们保留了原来的 3，改变了其他 4 根柱子，所以需要 4 次操作。

解题思路

这个问题呀，其实是在考验我们的逆向思维哦，喵~

我们要最小化操作次数，这听起来有点麻烦。不如换个角度想想？最小化操作次数，其实就等于最大化我们保留不动的柱子数量！对不对？我们要尽可能多地保留原来的柱子，这样需要修改的柱子就最少了。

好，那我们来看看，什么样的柱子可以被我们保留下来呢？

假设我们决定保留原来序列中的两个柱子，它们在原数组中的下标是 i 和 j，并且 i < j。

因为它们是保留下来的柱子，所以在最终的非递减序列里，它们的高度必须满足 h[i] <= h[j]。
又因为它们是来自于初始的非递增序列，所以它们的高度本身满足 h[i] >= h[j]。

要把这两个条件同时满足，h[i] <= h[j] 和 h[i] >= h[j]，唯一的可能性就是 h[i] = h[j] 啦！

这就像一个启示，喵！这说明，我们所有决定保留下来的柱子，它们在原始序列中的高度必须是完全相同的！

既然所有保留的柱子高度都得一样，那为了让保留的柱子数量最多，我们应该选择哪一个高度呢？当然是选择在原始序列中出现次数最多的那个高度啦！

比如说，如果序列是 [5, 4, 4, 2, 1]，高度 4 出现了 2 次，是出现次数最多的。我们就可以保留这两个高度为 4 的柱子，然后把其他柱子都改成 4，得到 [4, 4, 4, 4, 4]。这样就只操作了 3 次。

所以，解题步骤就是：

统计初始序列中每个高度出现的次数。
找到那个出现次数最多的高度，记下这个最大次数 max_freq。
我们总共有 n 根柱子，我们决定保留 max_freq 根，那么需要修改的柱子数量就是 n - max_freq。

这就是我们的答案啦！是不是很简单呢？(＾• ω •＾)

题解代码

这是本猫娘为你准备的 C++ 代码，里面有详细的注释哦~

cpp

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

// 这个函数用来解决单个测试用例，喵~
void solve() {
    int n;
    std::cin >> n;

    // 题目说 1 <= n <= 50 并且 1 <= h_i <= n。
    // 这意味着 h_i 的最大值也就是 50。
    // 我们可以用一个固定大小的数组来进行频率统计，非常方便！
    // 数组大小设为 51（对应下标 0 到 50）就足够了。
    std::vector<int> counts(51, 0);

    int max_freq = 0;
    // 读取 n 个柱子的高度，并统计它们的频率。
    for (int i = 0; i < n; ++i) {
        int h;
        std::cin >> h;
        counts[h]++; // 对应高度的计数器加一
        // 顺便记录下目前为止出现过的最大频率
        if (counts[h] > max_freq) {
            max_freq = counts[h];
        }
    }

    // 我们的目标是用最少的操作使数组非递减。
    // 就像我们刚才分析的，最少操作数 = 总数 - 最多保留数。
    // 最多能保留的柱子数量，就是出现次数最多的那个高度的数量，也就是 max_freq。
    // 所以，需要修改的柱子数量就是 n - max_freq。
    std::cout << n - max_freq << "\n";
}

int main() {
    // 这两行是为了让输入输出更快一点，在打比赛的时候很有用哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但也用到了几个很重要的基础知识点呢，让本猫娘来给你梳理一下吧！

贪心算法 (Greedy Algorithm)
- 我们的解题思路就是一种典型的贪心策略。我们没有去考虑所有可能的最终序列，而是做出了一个“局部最优”的选择：保留出现次数最多的元素。我们相信这个局部最优选择能导向全局最优解。在这道题里，这个贪心策略恰好是正确的！贪心算法的核心就是“每一步都做当前看起来最好的选择”。
频率统计 (Frequency Counting)
- 这是算法竞赛中非常非常常见的技巧！当需要知道一个集合中每个元素出现了多少次时，我们就要用到频率统计。
- 方法一：使用数组。如果元素的取值范围不大（比如这道题里高度 h_i 不会超过 50），用一个数组来当计数器是最简单高效的。数组的下标对应元素的值，数组里存的就是出现的次数。
- 方法二：使用哈希表。如果元素的取值范围很大，或者元素不是整数，我们就不能用数组了。这时可以用 C++ 中的 std::map 或 std::unordered_map 来统计频率。

好啦，今天的讲解就到这里啦！希望本猫娘的解释能帮到你。如果还有什么问题，随时可以再来问我哦！我们下次再见，喵~ (´｡• ᵕ •｡`) ♡

题目大意 ​

解题思路 ​

题解代码 ​

知识点介绍 ​

题目大意

解题思路

题解代码

知识点介绍