C. Grouping Increases - 题解

比赛与标签

比赛: Hello 2024 标签: data structures, dp, greedy, *1400 难度: *1400

题目解读喵~

主人你好呀~！这道题是说，我们有一个数组 a，需要把它所有的元素分到两个新的子序列 s 和 t 里去，原来的相对顺序不能变哦。我们的目标是最小化总的“惩罚值”，喵~

那什么是“惩罚值”呢？对于一个序列，比如 s，它的惩罚值 p(s) 就是序列里出现 s[i] < s[i+1] (也就是后面比前面大) 的次数。总惩罚值就是 p(s) + p(t)。

简单来说，我们就是要想办法把 a 的元素拆分到 s 和 t 里，让这两个序列尽可能地“不上升”。每次出现数字变大的情况，就会被罚一次，我们想被罚得最少，的说！

贪心的小猫爪一拍，思路就来啦！

这道题看起来有点复杂，但其实可以用一个很聪明的贪心策略来解决哦，喵~ 我们可以从左到右一个一个地处理数组 a 的元素，对于每个元素，我们都做出当前看起来最好的选择！

我们的状态其实只跟两个子序列 s 和 t 的最后一个元素有关，对吧？因为下一个元素放进来会不会产生惩罚，只取决于它和队尾那个元素的大小关系。

所以，我们只需要记住 s 的结尾元素 end1 和 t 的结尾元素 end2 就好啦。

为了让逻辑更清晰，我们不妨始终保持 end1 <= end2 这个好习惯。如果处理完一个数后 end1 > end2 了，我们就把它们交换一下，这样我们总是知道谁是那个更小的“门槛”，喵~

好了，现在我们来处理数组 a 里的当前元素 x：

1. 最理想的情况 (不产生惩罚): 我们希望把 x 接在某个序列后面，并且这个序列的结尾元素要大于等于 x。

   • 如果 x <= end1: 哇！x 比两个队尾都小（或者相等），那我们肯定选一个放进去。放到哪里更好呢？当然是放到结尾元素更小的那个序列（也就是 end1 所在的序列）啦！因为这样可以把 end1 更新成更小的 x，同时保留了较大的 end2，给后面可能出现的大数字留了更多余地。这绝对是当前最优的选择！所以我们更新 end1 = x。
   • 如果 end1 < x <= end2: x 没办法放在第一个序列了（会产生惩罚），但是可以放在第二个序列呀！这是我们唯一不产生惩罚的选择，那就快放进去吧！我们更新 end2 = x。

2. 没办法啦，必须接受惩罚的情况:

   • 如果 x > end2 (也就意味着 x > end1): 呜呜，x 比两个队尾都大，不管放哪里都要产生一次惩罚了。既然惩罚不可避免，我们就要为未来着想，让之后产生惩罚的可能性变得更小。我们应该把 x 放在哪个序列呢？我们应该选择替换掉那个更小的队尾，也就是 end1。为啥呢？因为这样做，我们把一个序列的结尾变成了 x，但另一个序列的结尾 end2 依然被保留了下来。保留一个尽可能大的结尾，对我们接纳未来的新元素更有利！所以，我们增加一次惩罚计数 penalty++，然后更新 end1 = x。

初始状态怎么设置呢？ 一开始两个序列都是空的，任何数字放进来都不会有惩罚。我们可以把 end1 和 end2 初始化成一个超级大的数，比如 n + 1 (因为题目说元素最大是 n)，这样第一个元素无论是什么，都可以轻松地放进第一个序列里啦！

总结一下我们的贪心策略就是：对于每个数，优先不产生惩罚；如果不行，就选择对未来最有利的方式（保留一个尽可能大的结尾）来接受惩罚。

把思路变成代码吧，喵！

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

void solve() {
    int n;
    std::cin >> n;

    // 初始化两个子序列的结尾元素，喵~
    // 我们用一个比任何 a_i 都大的数 (n+1) 来表示一个“无限大”的结尾，
    // 这样第一个元素总能找到地方放，不会产生惩罚。
    int end1 = n + 1;
    int end2 = n + 1;
    int penalty = 0;

    // 我们一个一个地处理数组 'a' 的元素，
    // 这样就不用把整个数组存下来啦，超级省内存的说！
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;

        // 为了简化逻辑，我们始终保持 end1 <= end2 这个状态。
        // 如果不是，就交换一下，这样思考起来更简单呐！
        if (end1 > end2) {
            std::swap(end1, end2);
        }

        // 这里就是我们贪心策略的核心啦！
        // 情况一：x 可以无惩罚地放入结尾是 end1 的序列。
        // 这是最棒的选择，因为它把一个结尾变得更小，给未来留下了更大的 end2。
        if (x <= end1) {
            end1 = x;
        } 
        // 情况二：x 不能放入第一个序列，但可以无惩罚地放入第二个序列。
        // 这是当前唯一不产生惩罚的选择，当然要选它啦！
        else if (x <= end2) {
            end2 = x;
        } 
        // 情况三：x 比两个结尾都大，惩罚不可避免了，呜~
        // 我们选择替换掉较小的结尾 end1，这样可以保留较大的 end2，
        // 为未来处理更多数字创造更好的条件！
        else {
            penalty++;
            end1 = x;
        }
    }

    std::cout << penalty << "\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) 的说！我们只需要遍历一次数组 a 的 n 个元素。在循环里，我们做的都是常数时间的比较、赋值和交换操作。所以对于每个测试用例，速度都是线性的，非常快哦！
• 空间复杂度: O(1) 的说！看我们的代码，根本没有把整个数组存下来！我们只用了几个变量 (n, end1, end2, penalty, x) 来记录当前状态。这真是太棒了，对内存非常友好，喵~

温故知新，总结一下知识点！

这道题真是个学习贪心思想的好例子呢！

1. 贪心算法 (Greedy Algorithm): 核心就是“活在当下”，每一步都做出局部最优解。在这道题里，就是优先选择不产生惩罚的放置方式，如果必须惩罚，就选择对未来影响最小的方式。
2. 状态简化: 我们发现解决问题并不需要知道两个子序列的全部内容，只需要它们的结尾元素。这是解决动态规划和贪心问题时一个非常重要的简化技巧！
3. 维护不变量 (Invariant): 我们通过 swap 操作始终保持 end1 <= end2。这让我们的 if-else 判断逻辑变得超级清晰，避免了复杂的分类讨论，是个很棒的编程习惯！
4. 在线处理 (Online Processing): 通过边读入边处理的方式，我们成功地将空间复杂度从 O(n) 优化到了 O(1)。当题目中的元素只需要依次处理，且不需要回头看时，这招非常好用！

希望这篇题解能帮到你哦，主人！如果还有其他问题，随时可以再来找我，喵~ >w<