题意
题目描述
对于(N)个整数(0,1, cdots ,N-1)，一个变换序列(T)可以将(i)变成(T_i)，其中(T_i in { 0,1,cdots, N-1})且(igcup_{i=0}^{N-1} {T_i } = {0,1,cdots,N-1 })，(forall x,y in {0,1,cdots , N-1})，定义(x)和(y)之间的距离(D(x,y)=min{|x-y|,N-|x-y|})。给定每个(i)和(T_i)之间的距离(D(i,T_i))，你需要求出一个满足要求的变换序列(T)。如果有多个满足条件的序列，输出其中字典序最小的一个。
说明：对于两个变换序列(S)和(T)，如果存在(p<N)，满足对于(i=0,1,cdots p-1)，(S_i=T_i)且(S_p<T_p)，我们称(S)比(T)字典序小。
输入输出格式
输入格式：
第一行包含一个整数(N)，表示序列的长度。接下来的一行包含(N)个整数(D_i)，其中(D_i)表示(i)和(T_i)之间的距离。
输出格式：
如果至少存在一个满足要求的变换序列(T)，则输出文件中包含一行(N)个整数，表示你计算得到的字典序最小的(T)；否则输出No Answer。注意：输出文件中相邻两个数之间用一个空格分开，行末不包含多余空格。
输入输出样例
输入样例：
5
1 1 2 2 1
输出样例：
1 2 4 0 3
说明
对于(30 \%)的数据，满足：(N leq 50)；
对于(60 \%)的数据，满足：(N leq 500)；
对于(100 \%)的数据，满足：(N leq 10000)。
思路
这题(5 mins)之内做不出来我吃屎。 --Uranus
...
时间到了，记得你打的赌啊。 --oyyz
这个故事告诉我们不要随便插(flag)。
进入正题。对于每一个(i)，显然有两个(T_i)可以满足(D(i,T_i)=D_i)，即：
题目询问的就是是否有一个序列(T)能满足上述要求且(T)为(0-(n-1))的一个排列。那么我们就可以用二分图匹配的方法来对(i)尽可能匹配(T_i)，从而得到是否有解。
那么如何让解满足字典序最小呢？想想二分图匹配中匈牙利算法的过程：尽量满足后匈牙利的点能够满足匹配，将前面匹配过的点向后移。我们就可以利用这个思路，反向匹配，那么就能达到字典序最优。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+514;
int n,to[MAXN][2],match[MAXN],inv[MAXN];
bool vis[MAXN];
int read()
{
int re=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
return re;
}
bool dfs(int now)
{
for(int i=0;i<2;i++)
{
int hjj=to[now][i];
if(!vis[hjj])
{
vis[hjj]=true;
if(match[hjj]==-1||dfs(match[hjj]))
{
match[hjj]=now,inv[now]=hjj;
return true;
}
}
}
return false;
}
int main()
{
n=read();
memset(match,-1,sizeof match);
for(int i=0;i<n;i++)
{
int x=read();
to[i][0]=(i+x)%n,to[i][1]=(i-x+n)%n;
if(to[i][0]>to[i][1]) swap(to[i][0],to[i][1]);
}
for(int i=n-1;i>=0;i--)
{
memset(vis,false,sizeof vis);
if(!dfs(i))
{
printf("No Answer");
return 0;
}
}
for(int i=0;i<n;i++) printf("%d ",inv[i]);
return 0;
}