Codeforces 892D(构造)

Codeforces 892D
题意:给出一个$a$数组,要求一个$a$的排列$b$,使得两个数组任意位置元素的和不同。
做法:使$b$中每个数都大于$a$(最大值必须对应最小值),那么就能保证两个数组任意位置元素的和不同。
证明:
1、$b$中每个数都大于$a$,那么两个数组任意位置元素的和不同
2、最大值对应最小值为什么对?因为$k$小于$n$。显然在$a$中不选完所有元素,就算包含了最大值,也不会相同。

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, a[25], b[25];
map<int, int> whw;
void clean() {
}
void solve() {
clean();
for (int i = 0; i < n; i++) scanf("%d", &a[i]), b[i] = a[i];
sort(b, b + n);
for (int i = 0; i < n; i++) whw[b[i]] = b[(i + 1) % n];
for (int i = 0; i < n; i++) printf("%d ", whw[a[i]]);
}
int main() {
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------