Codeforces 1312B: Bogosort

Codeforces 1312B C++ 一解.

分析

此题相当于排序数组后使两个有限数列 (一个是数列 ${1,2,\cdots,n}$, 一个是排序后的数组 $a_\mathrm{sorted}$) 的差各不相同. 一个很容易想到的构造方法是对一个单调 (不一定严格) 递减数列与严格单调递增数列求差, 这样得到的差数列的各元素一定各不相同 (且是单调递减的).

代码

#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int t, n, a[100];

    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
        }
        sort(a, a + n); // 先递增排列
        while (n--)
        {
            cout << a[n] << ' '; // 再倒序输出, 相当于 "构造" 出了递减数列
        }
        cout << endl;
    }

    return 0;
}