Codeforces Round #446 (Div. 2) D. Gluttony 構造 置換

http://codeforces.com/contest/892/problem/D

題意:給出一個長度為n的序列a,要求構造出一個序列b.

滿足a和b.下标相同的子序列(長度!=n),其和都不同. n<=22,a[i]<=1e9.

構造:若a[i]是序列的第j大 則令b[i]為序列的第j+1大(若a[i]為最大 則令b[i]為最小).

證明:現在任意選一組下标s={x1,x2...xk}

若s不含a最大值的下标 則b[x1,x2..xk] > a[x1,x2..xk]

若s含a最大值的下标 則s'={y1,y2..y[n-k]} b[y1,y2..y[n-k]]>a[y1..y[n-k]] 即b[x1...x[k]]<a[x1..x[k]]

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
	public static int gcd(int a,int b) {
		if(a<b) return gcd(b,a);
		if(a%b==0) 
			return b;
		return gcd(b,a%b);
	}
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int []a=new int[n];
		int []p=new int[n];
		int []b=new int[n];
		for(int i=0;i<n;i++){
			a[i]=input.nextInt();
			p[i]=a[i];
		}
		Arrays.sort(p);
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(a[i]==p[j]) {
					b[i]=p[(j+1)%n];
					break;
				}
			}
		}
		for(int i=0;i<n;i++) {
			System.out.printf("%d%c",b[i],i==n-1?'\n':' ');
		}

	}
}