Gluttony CodeForces - 892D (构造,思维)

题面:

You are given an array a with n distinct integers. Construct an array b by permuting a such that for every non-empty subset of indices S = {x₁, x₂, ..., x_k} (1 ≤ x_i ≤ n, 0 < k < n) the sums of elements on that positions in a and b are different, i. e.

这个题挺不错的, 只需要将每个元素按大小循环右移即可. 这里简单证明一下.

记序列$c_i=a_i-b_i$, 转化为判断$c$是否有一个真子集的和为0

一个显然的结论是序列$c$的和为0的, 并且只有一个数为负, 所以对于不含负数的子集和一定大于0, 包含负数的一定小于0

#include <iostream>

#include <algorithm>

#include <cstdio>

#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;

const int N = 2e5+10;

int a[N], b[N], f[N], n, m, k;

int main() {

	scanf("%d", &n);

	REP(i,1,n) scanf("%d", a+i),b[i]=a[i];

	sort(b+1,b+1+n);b[n+1]=b[1];

	REP(i,1,n) printf("%d ", b[lower_bound(b+1,b+1+n,a[i])-b+1]);

	puts("");

}

巴特西

Gluttony CodeForces - 892D (构造,思维)

最新文章

热门文章