很明显是二分图匹配,关键是怎么求字典序最小

想到两种做法,首先是直接匹配,然后从第一位贪心调整

第二种是从最后一个倒着匹配,每次匹配都尽量选小的,这样一定能保证字典序最小

 type node=record
po,next:longint;
end; var e:array[..] of node;
p,cx,cy:array[..] of longint;
v:array[..] of boolean;
i,n,len,x,y,s,d:longint; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; function dfs(x:longint):longint;
var i,y:longint;
begin
i:=p[x];
while i<> do
begin
y:=e[i].po;
if not v[y] then
begin
v[y]:=true;
if (cy[y]=) or (dfs(cy[y])=) then
begin
cx[x]:=y;
cy[y]:=x;
exit();
end;
end;
i:=e[i].next;
end;
exit();
end; begin
readln(n);
for i:= to n do
begin
read(d);
x:=i+d;
if x>n then x:=x-n;
y:=i-d;
if y< then y:=y+n;
if x>y then
begin
add(i,x);
add(i,y);
end
else begin
add(i,y);
if x<>y then add(i,x);
end;
end;
s:=;
for i:=n downto do
if cx[i]= then
begin
fillchar(v,sizeof(v),false);
s:=s+dfs(i);
end;
if s<n then writeln('No Answer')
else begin
for i:= to n do
begin
write(cx[i]-);
if i<>n then write(' ');
end;
end;
end.
05-08 15:32