题解 P1053 【篝火晚会】

The_Dark_Knight · 2016-10-26 16:00:25 · 题解

看到没有pascal的代码我就来凑一波了。这个方法是我在一个博客上面看到的。要找出移动几次，显然目标状态我们是需要求出来的。至于判断是否输出-1也很简单：如果说x希望y在他身边，而y希望的人里面没有x，那么显然强扭的瓜不甜（感觉没有哪不对），这时候怎么移动都没用。求出理想排列后，我们与原排列比较对齐，使原排列有尽量多的人不需要移动（即所处位置与目标位置一致），若有k个可以做到，那么显然移动代价就是n-k，要让n-k最小，显然要让k最大。求k的方法比较多（动规之类的），不过博客中的一种方法我也是推荐的：如果a和b的相对位置与序号的相对位置和c和d的相对位置与序号的相对位置相同，并无法确定a、b、c、d相对位置是否都与序号的相对位置相同。但是我如果知道a与其序号位置、b与其序号位置、c与其序号位置、d与其序号位置的差值都相等，就一定有a、b、c、d与序号的相对位置相等。因此用a[i]存储目标环中权值与序号差值为i的数的个数，最后找出最大值k，N-k即为解。同样要反向做一次。时空复杂度皆为O(N)。

方法来自：http://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/49529773

uses math;
var l,r:array[0..50000] of longint;//记录理想的两旁
    per:Array[0..60000] of longint;//记录理想位置
    z,f:Array[0..1000000] of longint;//正反各一次
    i,j,k,m,n,p,t,ans:longint;
procedure ed;
begin
    writeln(-1);
    halt;
end;
begin
    assign(input,'P1053.in');reset(input);
    readln(n);
    for i:=1 to n do
      readln(l[i],r[i]);
    for i:=1 to n do
    begin
        if (l[l[i]]<>i)and(r[l[i]]<>i) then ed;
        if (l[r[i]]<>i)and(r[r[i]]<>i) then ed;
    end;
    per[1]:=1;
    per[2]:=l[1];
    for i:=2 to n-1 do
      if per[i-1]=l[per[i]] then per[i+1]:=r[per[i]]
      else per[i+1]:=l[per[i]];//求理想排列
    for i:=1 to n do
    begin
        inc(z[(i-per[i]+n)mod n]);
        inc(f[(n-i-per[i]+n)mod n]);
    end;
    for i:=1 to n do
    begin
        ans:=max(ans,z[i]);
        ans:=max(ans,f[i]);
    end;
    writeln(n-ans);
end.