题目描述
给定一个数组 a1,a2,…,an。
如果数组 a 满足对于任意 1≤i<j≤n,j−aj≠i−ai 均成立,则称数组 a 是一个好数组。
现在,请你通过将数组 a 中的元素任意重新排序来使其变为一个好数组(当然,你也可以选择保留初始顺序)。
可以通过数组重排得到的好数组可能不止一个,你只需输出任意一个满足条件的即可。
例如,对于数组 [1,1,3,5],重排后的好数组有 [1,3,5,1],[3,5,1,1],[5,3,1,1] 等等,而不好的数组有 [3,1,5,1],[1,1,3,5],[1,1,5,3] 等等。
输入格式
第一行包含一个整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
每组数据输出一行结果,包含 n 个整数,表示重新排好顺序的好数组 a。
数据范围
1≤T≤100,
1≤n≤100,
1≤ai≤100,
保证数据一定有解。
样例
输入样例:
3
1
7
4
1 1 3 5
6
3 2 1 5 6 4
输出样例:
7
1 5 1 3
2 4 6 1 3 5
算法1
(排序) $O(nlogn)$
如果从大到小排序
前面的,数值和idnex做差,差值比较大
后面的,数值和index做差,差值比较小
时间复杂度
参考文献
Python3 代码
T = int(input())
for _ in range(T):
n = int(input())
nums = [int(x) for x in input().split()]
nums.sort(reverse = True)
for x in nums:
print(x, end = ' ')
print()
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T; cin >> T;
while(T --)
{
int n; cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i ++)
cin >> nums[i];
sort(nums.rbegin(), nums.rend());
for (int x : nums)
cout << x << ' ';
cout << endl;
}
return 0;
}
c++代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T; cin >> T;
while(T --)
{
int n; cin >> n;
int nums[n];
for (int i = 0; i < n; i ++)
cin >> nums[i];
sort(nums, nums + n, greater());
for (int x : nums)
cout << x << ' ';
cout << endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla