Description
Input
Output
Sample Input
5
1 1 2 2 1
1 1 2 2 1
Sample Output
1 2 4 0 3
HINT
30%的数据中N≤50;
60%的数据中N≤500;
100%的数据中N≤10000。
匈牙利裸题
因为要注意字典序
所以加边还有find的时候要注意一下先后顺序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N (10000+100)
using namespace std;
struct node
{
int to,next;
} edge[N*];
int n,x,from[N],to[N],head[N],num_edge,used[N],now,a[]; void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} bool check(int x,int y,int ans)
{
if (y< || y>=n) return false;
if (min(abs(x-y),n-abs(x-y))==ans) return true;
return false;
} bool find(int x)
{
for (int i=head[x];i!=;i=edge[i].next)
if (used[edge[i].to]!=now)
{
used[edge[i].to]=now;
if (!to[edge[i].to] || find(to[edge[i].to]))
{
to[edge[i].to]=x;
from[x]=edge[i].to;
return true;
}
}
return false;
} int main()
{
memset(used,0x7f,sizeof(used));
scanf("%d",&n);
for (int i=;i<=n-;++i)
{
scanf("%d",&x);
a[]=i+x,a[]=i-x,a[]=i+(n-x),a[]=i-(n-x);
sort(a+,a++);
if (check(i,a[],x))
add(i,a[]);
if (check(i,a[],x))
add(i,a[]);
if (check(i,a[],x))
add(i,a[]);
if (check(i,a[],x))
add(i,a[]); } int ans=;
for (int i=n-;i>=;--i)
{
now=i;
if (find(i)) ans++;
else break;
}
if (ans!=n)
printf("No Answer");
else
{
for (int i=;i<=n-;++i)
printf("%d ",from[i]);
printf("%d",from[n-]);
}
}