题目大意
给出元素$i$在排列$b$中的相对距离（如，与$2$相对距离为$1$的是$1,3$，与$1$相对距离为$2$的是$n-1,3$），求出字典序最小的$b$。
题目分析
显然我们可以建立起二分图模型。
左边的点代表$i$，右边的代表$b$中的元素，$x\rightarrow y$连边代表$b_x$可以为$y$。
然后我们便可以使用匈牙利算法构造出一组可行解。
然而题目要求字典序最小，不难想到一种贪心策略：
按照编号从大到小扩展交错路，每一次扩展交错路尽量选择编号小的元素匹配。
贪心策略的正确性：
如果我们尽量匹配编号小的点，在当前这次匹配一定是字典序最小的。
如果编号从大到小，那么我们可以保证编号小的匹配方案会尽量小，因为如果编号小的匹配方案已被编号大的占用，则会尝试将占用解除然后给编号小的匹配。
反之，若编号从小到大，则满足字典序最大。
byvoid大神还有一种神奇的$O(n)$算法，以后再学。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=20005;
int n,vst[maxn],My[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
bool Dfs(int Now) {
for(auto& Next:edges[Now]) {
if(vst[Next])continue;
vst[Next]=1;
if(My[Next]==0||Dfs(My[Next])) {
My[Next]=Now;
My[Now]=Next;
return true;
}
}
return false;
}
int Hungary() {
int ans=0;
for(int i=n; i>=1; i--) {
memset(vst,0,sizeof(vst));
ans+=Dfs(i);
}
return ans;
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int();
int t1=i+x,t2=i-x;
if(t1>n)t1-=n;
if(t2<1)t2+=n;
if(t1>t2)swap(t1,t2);
AddEdge(i,t1+n);
AddEdge(i,t2+n);
}
if(Hungary()!=n) {
puts("No Answer");
return 0;
}
for(int i=1; i<=n; i++)printf("%d ",My[i]-n-1);
return 0;
}
|
