喵呜~ 解决 Codeforces 1783A - A. Make it Beautiful 的小秘密！

各位小可爱们，喵呜~！今天我们一起来玩一个有趣的小游戏，是来自 Codeforces 的 1783A 题，叫做 "A. Make it Beautiful" 呢！听起来是不是就很美好呀？嘿嘿，跟着我一起来看看这个小谜题吧！

题目大意：这是个什么小挑战呀？

首先呀，我们得知道题目在说什么，对不对？

题目里说，有一个数组 a，它呀，如果满足某个条件，就会被叫做“丑陋的”数组（ugly array）。这个条件就是：如果数组里至少有一个元素，它恰好等于它前面所有元素的和。比如说，[6, 3, 9, 6] 就是丑陋的，因为 9 等于它前面的 6 + 3 呢！还有 [5, 5, 7] 也是丑陋的，因为第二个 5 等于它前面的 5。

那如果一个数组不丑陋，它就是“美丽的”数组（beautiful array）啦！比如 [8, 4, 10, 14] 就很美丽，因为 8 不等于 0（第一个元素前面没东西嘛），4 不等于 8，10 不等于 8 + 4，14 也不等于 8 + 4 + 10。

我们得到一个数组 a，它有一个特点哦：它里面的元素是非递减排序的，也就是说 a_1 <= a_2 <= ... <= a_n，而且所有元素都大于等于 1 呢。我们的任务就是，重新排列这个数组 a，让它变得美丽！我们不能添加或删除元素，只能改变它们的顺序。如果原数组本身就美丽，那保持不变也可以哦。

如果能做到，就打印 "YES"，然后打印一个美丽的排列；如果怎么都变不成美丽的，就打印 "NO"。

喵呜~ 听起来是不是有点像在玩积木呀？我们要把积木块重新堆放，让它们不要“碰巧”等于前面所有积木的高度总和呢！

喵咪的思考过程：怎么让它变美丽呢？

这个问题呀，看起来好像有点复杂，但是只要我们仔细观察，就会发现一些小秘密呢！

首先，题目给了我们一个很重要的提示：输入的数组 a 已经是非递减排序的啦（a_1 <= a_2 <= ... <= a_n）。而且所有元素都大于等于 1。

我们想想看，什么情况下一个数组会变得丑陋呢？假设我们排列好的数组是 b_1, b_2, ..., b_n。

第一个元素 b_1：它前面没有元素，所以前面元素的和是 0。因为 a_i >= 1，所以 b_1 肯定大于等于 1，它不可能等于 0。所以第一个元素永远不会让数组变丑陋，喵~！
第二个元素 b_2：如果 b_2 = b_1，那数组就丑陋啦！
第三个元素 b_3：如果 b_3 = b_1 + b_2，那数组就丑陋啦！
以此类推，如果 b_k = b_1 + b_2 + ... + b_{k-1}，就丑陋啦！

喵呜~ 什么时候会“不可能”呢？

我们来考虑最坏的情况，就是什么时候我们无论怎么排列，都无法让数组变美丽。如果数组里所有的元素都一模一样，比如说 [C, C, C, ..., C]。我们随便怎么排列，得到的数组还是 [C, C, C, ..., C]。

第一个元素是 C。前面和是 0。C != 0 (因为 C >= 1)。没问题。
第二个元素是 C。前面和是 C。哎呀！C 等于 C 了！这个数组就丑陋了！
而且，无论怎么排列，第二个元素总是 C，第一个元素也总是 C，所以 b_2 总是等于 b_1。
所以，如果数组里所有元素都相同，那它就永远是丑陋的，无法变成美丽的！喵呜~！

我们怎么知道所有元素都相同呢？因为输入的数组是排序好的嘛，所以只要检查 a[0]（最小的那个）是不是等于 a[n-1]（最大的那个）就行啦！如果它们相等，就说明所有元素都相等。这种情况下，我们就得乖乖地打印 "NO" 啦。

喵呜~ 什么时候可以“变美丽”呢？

如果 a[0] 不等于 a[n-1]，那就说明数组里有不同的元素，也就是说 a[0] < a[n-1]。这种情况下，我们有没有办法构造一个美丽的数组呢？

来，跟着我的小爪子，我们试试看这个排列方法：把数组里最大的那个元素 a[n-1] 放在最前面，然后把剩下的元素 a[0], a[1], ..., a[n-2] 按照它们原来的顺序（从小到大）依次放在后面。所以，我们构造的新数组 b 就会是这样子（假设数组下标从0开始）： b = [a[n-1], a[0], a[1], ..., a[n-2]]

我们来验证一下，这个排列是不是总是美丽的呢？

检查 b_0 (也就是 a[n-1])： 它是第一个元素，前面元素的和是 0。因为 a[n-1] >= 1，所以 a[n-1] 肯定不等于 0。没问题！
检查 b_1 (也就是 a[0])： 它前面元素的和是 b_0，也就是 a[n-1]。我们当前处理的是 a[0] < a[n-1] 的情况。所以 a[0] 肯定不等于 a[n-1]。没问题！
检查 b_k (对于 k >= 2，也就是 a[k-1]，用 0-based index)：b_k 前面元素的和是 S_{k-1} = b_0 + b_1 + ... + b_{k-1}。根据我们的构造，S_{k-1} = a[n-1] + a[0] + a[1] + ... + a[k-2]。我们要比较 b_k = a[k-1] 和 S_{k-1}。因为原始数组 a 是非递减排序的，所以 a[k-1] 肯定小于等于 a[n-1] (因为 k-1 <= n-1 嘛)。同时，S_{k-1} 呢，它等于 a[n-1] 加上 a[0] 和后面的一些元素。因为 a[0] >= 1，所以 S_{k-1} 肯定会比 a[n-1] 严格大！所以，我们有 b_k = a[k-1] <= a[n-1] < S_{k-1}。喵呜~ 这样一来，b_k 永远不可能等于 S_{k-1} 啦！

所以呀，这个构造方法 [a[n-1], a[0], a[1], ..., a[n-2]] 在 a[0] < a[n-1] 的时候总是能得到一个美丽的数组！太棒了，是不是很简单呀？

题解方法：喵咪的魔法步骤！

总结一下我们的魔法步骤：

读入数据：先读入数组的长度 n，然后把 n 个整数 a_1, ..., a_n 都读进来。
判断特殊情况：检查一下 a[0] 和 a[n-1]。
- 如果 a[0] 等于 a[n-1]（也就是说，数组里所有数字都一样），那就没办法啦，直接打印 "NO"。
构造美丽数组：
- 如果 a[0] 不等于 a[n-1]，那么就说明我们可以构造一个美丽的数组！
- 先打印 "YES"。
- 然后，按照我们发现的“魔法顺序”打印元素：先打印 a[n-1]（最大的那个元素），接着打印 a[0], a[1], ..., a[n-2]（剩下的元素从小到大）。
- 记得元素之间要用空格隔开哦，最后要换行！

就是这么简单，喵~！

C++ 代码实现：喵呜~ 看看我的代码！

cpp

#include <iostream> // 用来输入输出，比如 cin 和 cout
#include <vector>   // 用来使用动态数组 std::vector
#include <numeric>  // 虽然这个题解没用到，但有时候做数学运算会用到哦
#include <algorithm> // 虽然这个题解没用到，但有时候排序啊查找啊会用到呢

void solve() {
    int n;
    std::cin >> n; // 读入数组的长度 n
    std::vector<int> a(n); // 创建一个大小为 n 的整数向量（数组）
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i]; // 循环读入数组的每个元素
    }

    // 题目保证了输入数组 'a' 是非递减排序的哦。
    // 一个数组如果某个元素等于它前面所有元素的和，就是丑陋的。

    // 情况1：如果数组里所有元素都一样
    // 因为数组是排序好的，所以只要看第一个元素和最后一个元素是不是一样就行啦
    if (a[0] == a[n - 1]) {
        std::cout << "NO\n"; // 喵呜~ 没办法了，打印 NO
        return; // 结束这个测试用例
    }

    // 情况2：如果数组里有不同的元素（也就是 a[0] < a[n-1]）
    // 这种情况下，我们总能构造一个美丽的数组！
    // 构造方法是：把最大的元素放在最前面，然后跟着剩下的小元素们
    // 比如，原数组 a = [a_0, a_1, ..., a_{n-2}, a_{n-1}]
    // 新数组 b = [a_{n-1}, a_0, a_1, ..., a_{n-2}]
    std::cout << "YES\n"; // 喵~ 可以做到，打印 YES

    // 打印我们构造的美丽数组
    std::cout << a[n - 1]; // 先打印最大的那个元素
    for (int i = 0; i < n - 1; ++i) {
        std::cout << " " << a[i]; // 然后依次打印剩下的元素，前面加个空格哦
    }
    std::cout << "\n"; // 最后记得换行！
}

int main() {
    // 这两行是用来加速输入输出的，平时写竞赛题都会加上呢，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 读入测试用例的数量 t
    while (t--) { // 循环处理每个测试用例
        solve(); // 调用 solve 函数来解决当前的测试用例
    }
    return 0; // 程序完美结束！
}

这段代码是不是清晰又简洁呢？喵呜~ 就像我的小爪子一样灵活！

和题目有关的知识点：喵喵小课堂！

这个问题主要考察的是一些基础的数学观察能力和构造性算法。

贪心思想（Greedy Approach）：虽然我们没有明确说这是贪心，但我们选择把最大的元素放在最前面，就是一种尝试“最大化”后面前缀和，从而让后续元素难以等于前缀和的策略。这有点像贪心算法的局部最优选择。
前缀和（Prefix Sum）：题目中“前面所有元素的和”本质上就是前缀和的概念。虽然我们没有显式计算整个前缀和数组，但理解这个概念有助于我们分析为什么 b_k 不等于 S_{k-1}。
排序数组的性质：题目明确说了输入数组是排序的，这是解决问题的关键！它让我们可以非常容易地判断所有元素是否相同 (a[0] == a[n-1])，并且在构造新数组时，利用 a[i] <= a[j] (如果 i < j) 这个性质来证明我们的构造是正确的。
特判（Edge Cases）：处理所有元素都相同的情况，这是一种常见的特判。在算法设计中，识别并单独处理这些特殊情况通常能简化问题。
构造性问题：这类问题要求我们“构造”一个满足条件的解，而不是仅仅判断是否存在或计算某个值。通常需要找到一个简单而通用的构造方法，并证明其正确性。

喵呜~ 希望这篇题解能帮助小可爱们更好地理解这道题呢！下次我们再一起玩别的编程游戏吧！拜拜~！

喵呜~ 解决 Codeforces 1783A - A. Make it Beautiful 的小秘密！ ​

题目大意：这是个什么小挑战呀？ ​

喵咪的思考过程：怎么让它变美丽呢？ ​

喵呜~ 什么时候会“不可能”呢？ ​

喵呜~ 什么时候可以“变美丽”呢？ ​

题解方法：喵咪的魔法步骤！ ​

C++ 代码实现：喵呜~ 看看我的代码！ ​

和题目有关的知识点：喵喵小课堂！ ​