Dashboard - Codeforces Round 897 (Div. 2) - Codeforces

A - green_gold_dog, array and permutation

题意

有一个长度为n的数组a，请你找出一个长度为n的排列b。 根据数组a和b来构造出数组c。
$c[i] = a[i] - b[i]$ ，尽可能地使c数组中的 互不相同的数的数量。

思路

好妙的思路！ 让最小的$a[i]$ 减去n,次小的减去$n-1$ ,这样每个$c[i]$ 都不一样。

代码

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
30
31
32
33
34
35
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 4e4 + 5;
pair<int,int> a[N];
pair<int,int> b[N];
int main(){
	int t;
	cin>>t;
	while (t--){
		int n;
		cin>>n;
		int num;
		for(int i = 1;i<=n;i++){
			cin>>num;
			a[i].first = num;
			a[i].second = i;
		}
		sort(a+1,a+1+n);
		for(int i = 1;i<=n;i++){
			b[i].first = a[i].second;
			b[i].second = n+1-i;
		}
		sort(b+1,b+1+n);
		for(int i = 1;i<=n;i++){
			cout<<b[i].second <<" ";
		}
		puts("");
	}

	
	return 0;
}