Codeforces 1312B: Bogosort

Codeforces 1312B C++ 一解.

分析

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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;
}
Posted on

2022-07-30

Updated on

2022-07-30

Licensed under

Comments