题意：
给你 (n) 个数 (0,1,...n-1), 定义 (D(x,y) = min(|x-y|,n-|x-y|)) ,让你求一个序列 (T), 满足
(D(i,T_i) = d) ,且 (T_iin {0,1,2,...n-1}) , (T_i) 中的数不能重复。
让你求一个字典序最小的满足条件的序列 (T) 。
solution
我们对于 (i) 号点向 满足第 (i) 个位置条件的 (T_i) 连边。显然这会构成一个二分图。如果最大匹配数小于 (n) 显然无解。
考虑怎么构造出字典序最小的一组方案，在进行匈牙利算法的时候，我们后面进行匹配的点会覆盖掉前面的已经匹
配上的点, 因此我们可以从后往前倒着匹配。然后 对于符合条件的 (T_i) ,按从大到小排序，依次加入到邻接表中，这
样我们在进行匈牙利算法的时候就会优先匹配字典序较小的点。最后字典序最小的方案就可以构造出来了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int n,m,tot,ans;
int head[N],d[N],a[N],match[N],b[N];
bool vis[N];
struct node
{
int to,net;
}e[200010];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void add(int x,int y)
{
e[++tot].to = y;
e[tot].net = head[x];
head[x] = tot;
}
int dis(int x,int y)
{
return min(abs(x-y),n-abs(x-y));
}
bool pd(int x)
{
return x >= 1 && x <= n;
}
bool dfs(int x)
{
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(!vis[to])
{
vis[to] = 1;
if(!match[to] || dfs(match[to]))
{
match[to] = x;
return 1;
}
}
}
return 0;
}
int main()
{
n = read();
for(int i = 1; i <= n; i++) d[i] = read();
for(int i = 1; i <= n; i++)
{
int num = 0;
if(dis(i,i+d[i]) == d[i] && pd(i+d[i])) a[++num] = i + d[i];
if(dis(i,i-d[i]) == d[i] && pd(i-d[i])) a[++num] = i - d[i];
if(dis(i,i+(n-d[i])) == d[i] && pd(i+(n-d[i]))) a[++num] = i + (n - d[i]);
if(dis(i,i-(n-d[i])) == d[i] && pd(i-(n-d[i]))) a[++num] = i - (n - d[i]);
sort(a+1,a+num+1);
for(int j = num; j >= 1; j--) add(i,a[j]+n), add(a[j]+n,i);
}
for(int i = n; i >= 1; i--)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
if(ans != n) printf("No Answer
");
else
{
for(int i = n+1; i <= 2*n; i++) b[match[i]] = i-n-1;
for(int i = 1; i <= n; i++) printf("%d ",b[i]);
}
printf("
");
return 0;
}