Moe's CF Life

喵~ 主人，欢迎回来！今天我们来看一道有趣的构造题，Codeforces 2117B - Shrink。这道题就像是和数字玩捉迷藏，要把它们一个个藏起来，直到藏不下为止，很有趣的喵！就让本猫娘带你一步步解开它的谜底吧！(^・ω・^)

题目大意

这道题给了我们一个叫做 “Shrink” (收缩) 的操作，可以对一个数组进行。操作规则是这样的：

在一个大小为 m 的数组 a 中，找到一个索引 i（这个索引不能是第一个也不能是最后一个，也就是 2 \le i \le m-1）。
这个位置的元素 a_i 必须比它左边的邻居 a_{i-1} 和右边的邻居 a_{i+1} 都大，也就是 a_i > a_{i-1} 并且 a_i > a_{i+1}。
如果找到了这样的 a_i，就可以把它从数组里拿走。

我们称一个排列（就是 1 到 n 的数字不重复不遗漏地排成一列）的分数，是它能执行 “Shrink” 操作的最大次数。

任务： 给定一个整数 n，我们需要构造一个长度为 n 的排列，让它的分数尽可能高。

简单来说，就是要我们想个办法排列 1 到 n 这些数字，使得我们能尽可能多次地移除那些“山峰”一样的数字喵。

解题思路

首先，我们来想想最多能操作多少次呢？每次操作都会让数组的长度减 1。操作的条件是元素不能在数组的两端，所以数组的长度至少要为 3。当数组只剩下 2 个元素时，就再也不能进行任何操作了。所以，从一个长度为 n 的数组开始，最多可以移除 n-2 个元素。我们的目标就是构造一个排列，让它真的能实现这 n-2 次操作！

那么，什么样的数字最容易成为“山峰”呢？当然是最大的数字啦！喵~ 比如数字 n，它比 1 到 n-1 的任何数都大。只要我们不把它放在数组的开头或者结尾，它就一定比它的邻居大，我们就可以第一个把它移除。

这给了我们一个很棒的贪心思路：每次都移除当前数组里最大的那个数。

为了实现这个想法，我们可以倒着想：

我们希望最后剩下两个数。让它们是 1 和 2 好了。
在它们被剩下之前，我们移除的最后一个数应该是 3。为了能移除 3，它必须在 1 和 2 中间，形成 [1, 3, 2] 或者 [2, 3, 1] 这样的结构。
再往前一步，我们移除了 4。在移除 4 之前，4 必须是一个山峰。比如，当时的数组可能是 [1, 4, 3, 2]。移除 4 之后，就变成了 [1, 3, 2]，正好是我们上一步的状态！
再往前，我们移除了 5。当时的数组可能是 [1, 5, 4, 3, 2]... 咦，不对，这个排列里 5 不是山峰。

看来倒着推有点复杂，我们还是顺着来吧。怎么构造一个排列，让我们能依次移除 n, n-1, n-2, \dots, 3 呢？

我们来试试这个结构：[1, 3, 4, 5, ..., n, 2]

让我们用 n=6 作为例子来看看这个排列 [1, 3, 4, 5, 6, 2] 的表现：

初始排列: [1, 3, 4, 5, 6, 2]
- 当前最大的数是 6。它的邻居是 5 和 2。6 > 5 且 6 > 2，太棒了！6 是一个山峰，可以移除。
- 移除 6 后，数组变成: [1, 3, 4, 5, 2]
第一步后: [1, 3, 4, 5, 2]
- 当前最大的数是 5。它的邻居是 4 和 2。5 > 4 且 5 > 2，完美！5 也是一个山峰，移除它。
- 移除 5 后，数组变成: [1, 3, 4, 2]
第二步后: [1, 3, 4, 2]
- 当前最大的数是 4。它的邻居是 3 和 2。4 > 3 且 4 > 2，又是一个山峰！移除 4。
- 移除 4 后，数组变成: [1, 3, 2]
第三步后: [1, 3, 2]
- 当前最大的数是 3。它的邻居是 1 和 2。3 > 1 且 3 > 2，最后的山峰！移除 3。
- 移除 3 后，数组变成: [1, 2]
最后: [1, 2]
- 只剩下两个元素了，游戏结束喵~

我们成功进行了 4 次操作，对于 n=6，正好是 n-2 次！这个构造看起来非常有效。

为什么这个构造总是有效的呢？

我们把最大的数 n 放在了 n-1 和 2 的旁边（在 [1, 3, ..., n-1, n, 2] 这个序列里）。因为 n 是老大，所以它肯定比邻居大，第一个被移除。
移除 n 后，序列变成了 [1, 3, ..., n-1, 2]。现在的老大是 n-1，它的邻居变成了 n-2 和 2。因为 n \ge 3，所以 n-1 \ge 2。只要 n>3，就有 n-1 > 2。所以 n-1 也比它的新邻居大，可以被移除。
这个过程会一直持续下去。每当我们移除当前最大的数 k 时，它的邻居总是 k-1（或者在移除3的时候是1）和 2。因为 k > k-1 且 k > 2（对于所有 k \ge 3），所以它总能被移除。
最终，我们移除了 n, n-1, \dots, 3，共 n-2 个数，达到了最大操作次数！

所以，我们的策略就是构造 [1, 3, 4, ..., n, 2] 这个排列。

题解代码

这是把上面的思路变成代码的样子，非常简单直观哦~

cpp

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

void solve() {
    int n;
    std::cin >> n;
    
    // 我们的神奇构造法喵！
    // 先把 1 放出来
    std::cout << 1 << " ";
    
    // 然后把 3, 4, ..., n 依次放出来
    for (int i = 3; i <= n; ++i) {
        std::cout << i << " ";
    }
    
    // 最后把 2 放出来当“刹车片”~
    std::cout << 2 << std::endl;
}

int main() {
    // 加速一下，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

题目大意 ​

解题思路 ​

题解代码 ​

相关知识点 ​

题目大意

解题思路

题解代码

相关知识点