Moe's CF Life

喵哈喽~ 主人，今天我们来解决一个关于给 Sage 买生日礼物的问题呀！Sage 想要买很多很多的冰球球，而我们的任务就是重新排列这些冰球球，让她能买到最多数量的“便宜”冰球球，喵~

题目大意

简单来说，就是有一排 n 个价格不同的冰球球。一个冰球球如果比它左边和右边的邻居都便宜，那它就是“便宜”的。最左边和最右边的球球因为只有一个邻居，所以肯定不是“便宜”的。

我们的任务是：

找到一种排列方式，使得“便宜”的冰球球数量最多。
输出这个最多的数量。
输出这种排列方式下，冰球球的价格顺序。

举个例子，如果价格是 (3, 1, 4, 2, 5)，那么价格为 1 的球球，它的邻居是 3 和 4，都比它贵，所以它是便宜的。价格为 2 的球球，邻居是 4 和 5，也比它贵，所以它也是便宜的。这样 Sage 就能买到 2 个球球啦！

题解方法

喵~ 想要让一个冰球球变得“便宜”，就要让它两边的球球都比它贵，对吧？这就像是把一个小不点夹在两个大个子中间：大 > 小 < 大。

为了让便宜的球球最多，我们就要尽可能多地创造这种 大 > 小 < 大 的结构。最理想的队形就是 大小大小大小 ... 这样子。

那要怎么实现呢？一个很自然的想法就出现啦：

排序：我们先把所有冰球球的价格从小到大排个队。这样我们就能非常清楚地知道哪些是“小不点”，哪些是“大个子”了，喵~
分组：排好序之后，价格靠前的是小球球，价格靠后的是大球球。
构造：现在我们来玩穿珠子的游戏！我们把数组分成两半，一半是较小的数，一半是较大的数。然后我们从“较大”的那一半里拿一个，再从“较小”的那一半里拿一个，交替着放进新的队伍里。

比如说，有 n 个球球。我们最多能构造出多少个便宜的球球呢？每个便宜的球球都需要两个比它大的邻居，而且便宜的球球不能相邻。所以 大小大小 ... 这样的结构是最优的。观察一下，n=5 时，大小大小大，可以有两个 小。 n=6 时，大小大小大大，也可以有两个 小。看起来，最多能有 (n-1)/2 个便宜的球球呢！

所以我们的策略就是：

将价格数组 a 排序。
最多能获得的便宜球球数量是 k = (n - 1) / 2。
这 k 个便宜的球球，我们当然是选价格最小的 k 个啦！也就是排序后数组的 a[0] 到 a[k-1]。
用来夹住它们的大球球，我们就从剩下的 n-k 个较大的数里选。
一个简单的构造方法是：把 n-k 个较大的数和 k 个较小的数穿插起来。
- 我们先放一个大数，再放一个小-数，再放一个大数，再放一个小数...
- 具体的实现就是，我们用两个指针，一个指向较小数的开头 (a[0])，一个指向较大数的开头 (a[k])。轮流从这两个地方取数，组成新的排列。
- 最后把剩下没用完的大数全部放到队尾就可以啦。

这样构造出来的 a[k], a[0], a[k+1], a[1], ... 序列，对于任意 a[i] (i < k)，它的邻居都是 a[k+i] 和 a[k+i+1]（或者类似的组合），因为排序过，所以这些大数肯定都比 a[i] 大，完美满足条件，喵~

题解

下面就是具体的 C++ 代码实现啦，主人请看~

cpp

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 1. 先把价格从小到大排好队，喵~
    std::sort(a.begin(), a.end());

    // 2. 计算最多能有多少个便宜的球球
    // 这个数量是 (n-1)/2
    int k = (n - 1) / 2;
    std::cout << k << "\n";

    // 3. 开始构造新的排列啦！
    std::vector<int> res(n);
    int res_idx = 0;   // 新数组 res 的指针
    int small_idx = 0; // 指向最小的 k 个数 (a[0]...a[k-1])
    int large_idx = k; // 指向剩下的 n-k 个大数 (a[k]...a[n-1])

    // 4. 像穿珠子一样，一个大球球，一个小球球...
    // 我们把 k 个小数和 k 个大数穿插起来
    while (small_idx < k) {
        res[res_idx++] = a[large_idx++]; // 放一个大数
        res[res_idx++] = a[small_idx++]; // 放一个小数
    }

    // 5. 把剩下还没用的大数都放到队尾去
    while (large_idx < n) {
        res[res_idx++] = a[large_idx++];
    }

    // 6. 把我们精心排列好的队伍打印出来~
    for (int i = 0; i < n; ++i) {
        std::cout << res[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速一下输入输出，跑得更快哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

知识点介绍

这个问题虽然看起来是排列组合，但核心思想其实很简单哦，主要涉及了以下几个知识点：

贪心算法 (Greedy Algorithm) 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。在这个问题里，我们的“贪心”体现在：
- 为了让一个球变得便宜，我们贪心地用当前能找到的、足够大的数来当它的邻居。
- 为了让便宜的球尽可能多，我们贪心地选择最小的那些数来充当“便宜球”。事实证明，这种局部最优的选择最终导向了全局最优解，喵~
排序 (Sorting) 排序是解决这个问题的基石。如果不先对价格进行排序，我们就很难有效地分辨出哪些是“小”价格，哪些是“大”价格。排序之后，数组就变得非常有规律，我们可以轻松地把数分成两组，为后续的构造算法提供了极大的便利。这在很多算法问题中都是预处理的关键一步哦！
构造算法 (Constructive Algorithm) 这类问题不只是要求一个数值解（比如最大数量），还要求你给出一个满足条件的具体方案（比如这个排列本身）。我们的解法就是一步步地构建出这个最优排列，所以它属于构造算法。我们根据推导出的性质（大夹小），来搭建最终的答案。

好啦，这次的题解就到这里啦！主人是不是完全明白了呀？以后有其他问题也随时可以来找我哦，喵~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍