(上不了p站我要死了,侵权度娘背锅)
(要不是我看不懂它在变什么。。。)
实际上就是对其中每个元素进行加di mod n或者是减di加n后mod n的操作。
那么每个元素都对应两个元素。而新的序列要求是排列,即不能有相同的。想到二分图匹配,就可得到一一对应的关系。
至于如何输出最小字典序,就要看对匈牙利算法的熟悉度和理解深度了。首先是考虑越靠前的数字要尽量对应小的数,而匈牙利在跑的时候是优先匹配先扫描到的边。如果先让前面的数字匹配小的数,之后在“腾”的时候就可能让前面的数的匹配变大,这样就不优了。但如果让前面的数字先匹配大的数,之后也不一定让它与小的数配对。
那该怎么办呢。。。
于是又发现,越后匹配的其实优先级越高,在扫边的时候会优先用先扫到的边进行匹配。所以这道题就从后往前for进行匹配,每次优先for小的边(这个就和建边的顺序有关了)
AC(PE*1)代码(要注意这道题要求了行末无空格)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
template <typename T>inline void read(T &res){
T k=1,x=0;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
res=x*k;
}
const int N=10000+5;
int n,d[N];
int head[N],to[N*2],nxt[N*2],hh=0;
bool vis[N];
int bl[N],has[N];
void adde(int a,int b){
hh++;
to[hh]=b;
nxt[hh]=head[a];
head[a]=hh;
}
bool find(int u){
if(u==-1) return true;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(vis[v]) continue;
vis[v]=1;
if(bl[v]==-1||find(bl[v])){
bl[v]=u;
has[u]=v;
return true;
}
}
return false;
}
int main(){
read(n);
for(int i=0;i<n;i++) read(d[i]);
for(int i=0;i<n;i++){
int x=(i+d[i])%n,y=(i-d[i]+n)%n;
if(x>y) swap(x,y);
adde(i,y),adde(i,x);
}
int cnt=0;
memset(bl,-1,sizeof(bl));
for(int i=n-1;i>=0;i--){
memset(vis,0,sizeof(vis));
if(find(i)) cnt++;
}
if(cnt<n){
printf("No Answer\n");
return 0;
}
for(int i=0;i<n-1;i++){
printf("%d ",has[i]);
}
printf("%d",has[n-1]);
return 0;
}