现在有一个 1n 的排列 A ,你需要构造一个 1n 的排列 B ,使得 ∑ni=1min(Ai,Bi) 最小。(n<=1000000)
输入
第一行一个整数 n。
第二行 n 个整数表示序列 A。
输出
输出 n 个整数表示序列 B,如果有多个满足要求的 B,输出字典序最小的那个。
数据范围
对于前 20% 的数据,有 n <= 10。
对于前 40% 的数据,有 n <= 10^3。
对于另外 10% 的数据,保证 A 是个递增序列。
对于 100% 的数据,有 1 <= n <= 10^6,A 是 1 ~ n 的排列。
输入样例
3
1 2 3
输出样例
2 3 1
样例解释
∑ni=1min(Ai,Bi)=4,可以证明这个值不可能变得更小。
#include<iostream>
#include<cstdio>
using namespace std;
void print_permutation(int n,int *A,int cur)
{
if(cur==n)
{
for(int i=0;i<n;i++)
printf("%d",A[i]);
printf("\n");
}
else for(int i=1;i<=n;i++)
{
int ok=1;
for(int j=0;j<cur;j++)
if(A[j]==i)
ok=0;
if(ok)
{
A[cur] =i;
print_permutation(n,A,cur+1);
}
}
}
int main()
{
int n=5,A[11]={1,2,3,4,5,6,7,8,9,10};
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&A[i]);
print_permutation(n,A,0);
return 0;
}
```