O(n^2)算法:匈牙利暴力水过
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; ////////////////////////////////////////////////// int n; int a[10001]; struct edge { int v,next; }e[20001]; int k; int head[10001]; int pre[10001]; bool vis[10001]; ////////////////////////////////////////////////// void adde(int u,int v) { e[k].v=v;e[k].next=head[u];head[u]=k++; } bool cmp(int a,int b){return a>b;} bool hungary(int u) { int v; for(int i=head[u];i!=-1;i=e[i].next) { v=e[i].v; if(vis[v]) continue; vis[v]=1; if(pre[v]==-1||hungary(pre[v])) { pre[v]=u; return 1; } } return 0; } ////////////////////////////////////////////////// void input() { memset(head,-1,sizeof(head)); memset(pre,-1,sizeof(pre)); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); } void solve() { //init int a,b; int num[5]; //calculate for(int i=0;i<n;i++) { a=::a[i]; b=n-a; num[1]=i-a; num[2]=i+a; num[3]=i-b; num[4]=i+b; for(int j=1;j<=4;j++) if(num[j]<0||num[j]>=n) { num[j]=-n*2; } sort(&num[1],&num[5],cmp); adde(i,num[1]);//大 adde(i,num[2]);//小 } //output for(int i=n-1;i>=0;i--) { memset(vis,0,sizeof(vis)); if(!hungary(i)) { puts("No Answer"); exit(0); } } int ans[10001]; for(int i=0;i<n;i++) ans[pre[i]]=i; for(int i=0;i<n-1;i++) printf("%d ",ans[i]); printf("%d\n",ans[n-1]); } ////////////////////////////////////////////////// int main() { #ifndef _TEST freopen("1562.in","r",stdin); freopen("1562.out","w",stdout); #endif input(); solve(); #ifdef _TEST for(;;); #endif return 0; }