补题 牛客小白月赛 73 [NC252702] 优美的序列

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

给出一个长度为 $n(1\leq n\leq 1000)$ 的序列 $a(1\leq a_i\leq 1000)$，一个序列是优美的需要满足以下条件：

  • 对于任意的 $1\leq i,j\leq n$，满足 $|a_i-a_j|\geq |i-j|$。

Kevin 现在有一个长度为 $n$ 的序列，你可以进行如下操作任意次：

  • 任选序列的两个下标 $i,j$（$i$ 与 $j$ 可以相同），然后交换 $a_i,a_j$ 的数值。

你需要使用上述操作（注意：你无需最小化操作的次数）帮他将这个序列变成优美的序列，或者告诉他该序列无法变成优美的序列。如果有多个可行的的答案，请输出任意一个。

输入描述

第一行包含一个整数 $T(1\leq T\leq 1000)$，表示测试用例的组数。

对于每组测试用例：

第一行包含一个整数 $n(1\leq n\leq 1000)$，表示序列的长度。

第二行包含 $n$ 个整数 $a_1\dots a_n\ (1\leq a_i\leq 1000)a1…an$，表示该序列。

保证对于所有的测试用例，$n$ 的总和不超过 $1000$。

输出描述

对于每组测试用例：

仅输出一行。如果该序列无法变成优美的序列，输出 $-1$；否则，输出 $n$ 个整数，表示使用上述操作后产生的优美的序列。如果有多个可行的的答案，请输出任意一个。

输入

1
2
3
4
5
2
2
1 1
1
100

输出

1
2
-1
100

题解

题目解析

一道构造题,分析条件 $|a_i-a_j|\geq |i-j|$ , 当数列中存在两个一样的数字的时候: $|a_i-a_j|=0$ 但是 $|i-j|>0$ , 当数列中每个数都不同的时候: 把数列从小到大排列,最极限的情况为 a[i] = i 显然 $|a_i-a_j|=|i-j|=0$ 满足条件,剩下的情况自然可以得到 $|a_i-a_j|\geq |i-j|$ 这一个条件.

于是我们得到这个题的解法了.与此同时,我们之前看jiangly的代码的时候学了 unique() 函数.那么现在,这个函数该发挥它的用处了.

AC代码

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
28
29
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define endl "\n"
using namespace std;
const int MAXN = 1010;

vector<int> v(MAXN);

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;
		for(int i=0;i<n;i++) cin >> v[i];
		sort(v.begin(),v.begin()+n);
		if(unique(v.begin(), v.begin()+n)-v.begin() == n){
			for(int i=0;i<n;i++) cout << v[i] << " ";
			cout << endl;
		}else{
			cout << -1 << endl;
		}
	}
	return 0;
}