Description

Input

Output

Sample Input

5

1 1 2 2 1

Sample Output

1 2 4 0 3

HINT

30%的数据中N≤50；

60%的数据中N≤500；

100%的数据中N≤10000。

 

题解：　　

　　二分图匹配模型很显然，但是不要看到二分图就去网络流了。。。注意到题目要求的是字典序最小的！如果你用Dinic算法去多路增广，根本无法保证字典序，除非用EK。据说也有边增广边调整的搞法，但是这么多花式搞法，前提都是你不知道匈牙利算法！匈牙利算法是一种非常简单的单路增广算法，不详解了。

　　这道题的重点在于你知道二分图匹配这个大专题之后怎么去求解。要求是字典序最小的解，这个很好解决。每次在插入边的时候，将字典序较大的边优先加入即可，每次优先匹配字典序较小的（因为后加入的先匹配）。

 

代码：

--------------------------------------------------------------------------------------------------

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

#define MAXN 20005

#define INF 0x3f3f3f3f

struct Edge { int v, next; } edge[MAXN];

int n, d, num[MAXN], ans[MAXN], vis[MAXN], now, h[MAXN];

void addEdge(int u, int v) { now++, edge[now] = (Edge) {v, h[u]}, h[u] = now; }

int DFS(int o)

{

　　for (int x = h[o]; x != -1; x = edge[x].next)

　　{

　　　　int v = edge[x].v;

　　　　if (!vis[v])

　　　　{

　　　　　　vis[v] = 1;

　　　　　　if (num[v] == -1 || DFS(num[v]))

　　　　　　{

　　　　　　　　ans[o] = v, num[v] = o;

　　　　　　　　return 1;

　　　　　　}

　　　　}

　　}

　　return 0;

}

void work()

{

　　int tot = 0;

　　for (int i = n - 1; i >= 0; i--)

　　{

　　　　memset(vis, 0, sizeof(vis));

　　　　if (DFS(i)) tot++; else break;

　　}

　　if (tot != n) printf("No Answer\n");

　　else for (int i = 0; i < n; i++) printf("%d ", ans[i]);

}

int x;

int main()

{

　　freopen("transform.in", "r", stdin);

　　freopen("transform.out", "w", stdout);

　　memset(ans, -1, sizeof(ans)), memset(num, -1, sizeof(num)), memset(h, -1, sizeof(h));

　　scanf("%d", &n);

　　for (int i = 0; i <= n - 1; i++)

　　{

　　　　scanf("%d", &x);

　　　　int v1 = i + x >= n ? (i + x) % n : i + x;

　　　　int v2 = i - x < 0 ? i - x + n : i - x;

　　　　if (v1 < v2) swap(v1,v2);

　　　　addEdge(i, v1), addEdge(i, v2);

　　}

　　work();

　　return 0;

}

--------------------------------------------------------------------------------------------------