如果发现广告等破坏行为，请尽量将条目恢复到较早的版本而不是把相应内容直接删除，谢谢合作。

USACO/sort3

来自"NOCOW"

跳转到: 导航, 搜索

目录

[编辑] 分析

用l[i]记录i(1,2,3)出现的个数。排序后一定是l[1]个1，l[2]个2，l[3]个3这3段。

sn[i,j]记录在第i段中的j的个数。第i段中的j和第j段中的i交换，两个元素交换，只需要一次。所以取sn[i,j]和sn[j,i]中的较小数s，累加到总交换数中。

这样交换后，剩下的肯定是3段同时交换，最少需要2次。我们只需累加(sn[1,2]+sn[1,3])×2即可。

Way2

这个题目的思路很简单:首先读入所有数,然后看原本的位置是’1′的里面有几个不是1,如果那几个不是1的数字在它原应该呆的位置中找到1的话就直接换,如果找不到就在另一堆中找…

比如说3 1 2三个数,第一个位置原应该是1,但是是3,那么就在原应该是3的位置中找1,但是是2,那么就在另一堆找,找到了1,那么把3跟1换一下…直到1全部到达自己的位置…然后在原应该是2的位置中找,如果碰到3就应该换一次….就这样找完就行了… 

 for i:=1 to n do
 begin
   readln(a[i]);
   if a[i]=1 then inc(s[1,2])
   else
   if a[i]=2 then inc(s[2,2]);
 end;

 s[2,1]:=s[1,2]+1;
 s[2,2]:=s[2,2]+s[2,1]-1;
 s[3,1]:=s[2,2]+1;

这段代码是记录位置的,s[x,1]是x的初始位置… s[x,2]是x的终点位置…

记录好位置之后就按照上面的流程去找就好了…实现起来应该是很简单的…


Way3

这是极其诡异的做法： 

   只要类似与方法二，记录下本是N的位置却不是N的个数A[N]，表示N这个数有多少个不在自己的位置上。
   然后，开一个数组B,存储排序后的序列。每次比较原数列Data[i] 和 B[i]，如果不相等,
      则dec(A[data[i]])
        dec(A[b[i]]);
      inc(Total)

本来只想着尝试这样的方法，没想到交上去后就AC了。 莫名。。只是求最小次数的问题这样可以AC。。 （本分版作者rock_li1）

Way4

By Etfl

O(n)预处理，O(1)计算

（注：数字i该在的位置即排序后数字i所在的位置区间）

d[i,j]表示排序后数字i该在的位置中含有的数字j的个数。

那么 

 ans:=d[2,1]+d[3,1]+d[2,3]+max(0,d[1,3]-d[3,1]);

原理很简单，首先要把所有的1交换到最前面:用的次数是d[2,1]+d[3,1]。然后把所有的3交换到最后，这些3共两部分：一部分是在2该在的位置中的，这些需要d[2,3]次交换；另一部分是在1该在的位置中的，这些3中有一些是通过处理1已经回来了，还有一些可能在处理1的时候交换到了2该在的位置，就需要再交换一下。这部分交换总数是max(0,d[1,3]-d[3,1])。

我用的是这个方式的变形: 

 ans:=d[1,2]+d[1,3]+max(d[2,3],d[3,2]);

处理解释： d[1,2]+d[1,3] 是所有占据 1位的2和3的数量，也就是不在正确位置的 1的数量（d[2,1]+d[3,1]），这两个加和是相同的。第一步求这个和，也就是让所有1归位。

此操作之后，存在两种情况。一：原序列中不存在 三值互换的现象，那么 d[2,3]与d[3,2]应该是相同的。max算子不起作用。

二:原序列中存在 三值互换的现象。可知，d[2,3]与d[3,2]中必有一个不变，而另一个在增大，且增大的量在数值上等于原三值交换的次数。就是例如上段文字所说：这些3中还有一些可能在处理1的时候交换到了2该在的位置，这时增加的就是d[2,3],而d[3,2]不变。由于交换是相对的，变化后的d'[2,3]与d'[3,2]必相等，又由于其中有一个值没有变动，所以该值也就等于原d[2,3]与d[3,2]中的最大值。

然后取这个最大值就可以让 2 3 同时归位。问题得解

[编辑] 补充一点

我们不用a[i,j]表示在i的位置上j的个数，比如a[2,1]=5就表示排好序后，上面应该是2，但现在被1占领的位置数是5。 先贪心到不能两值内部交换。

那么操作之后不会存在a[2,1]>0和a[2,3]>0同时成立的现象。

反证法:比如交换之后a[2,1]>0,且a[2,3]>0则在1的位置上只能有3(1和2能内部相抵的已经全部抵消了),3的位置上只能有1(同理),那么1和3又可以内部交换了，与假设矛盾。得证。

还有最后3值交换是乘2，而不是乘3。

[编辑] 参考代码

c++
c
pascal

[编辑] 引用

[1]

[2] { ID:liu777l1 PROG:sort3 LANG:PASCAL } 其实可以看做事一个贪心算法 不过不要去一步步地模拟 直接计算 快很多啊！ var 

 a:array [1..3,1..3] of longint;
 num:array [1..3] of longint;
 g:array [1..1000] of longint;
 total,i,j,k,l,n,m:longint;

begin 

 assign(input,'sort3.in'); reset(input);
 assign(output,'sort3.out'); rewrite(output);
 readln(n);
 for i:=1 to n do begin readln(g[i]); inc(num[g[i]]); end;
 for i:=1 to num[1] do inc(a[g[i],1]);
 for i:=(num[1]+1) to (num[1]+num[2]) do inc(a[g[i],2]);
 for i:=(num[1]+num[2]+1) to (num[1]+num[2]+num[3]) do inc(a[g[i],3]);
 total:=0;
 if (a[1,2]>a[2,1]) then begin inc(total,a[2,1]); a[1,2]:=a[1,2]-a[2,1];a[2,1]:=0; end
   else begin inc(total,a[1,2]); a[2,1]:=a[2,1]-a[1,2]; a[1,2]:=0; end;
 if (a[2,3]>a[3,2]) then begin inc(total,a[3,2]); a[2,3]:=a[2,3]-a[3,2];a[3,2]:=0; end
   else begin inc(total,a[2,3]); a[3,2]:=a[3,2]-a[2,3]; a[2,3]:=0; end;
 if (a[1,3]>a[3,1]) then begin inc(total,a[3,1]); a[1,3]:=a[1,3]-a[3,1];a[3,1]:=0; end
   else begin inc(total,a[1,3]); a[3,1]:=a[3,1]-a[1,3]; a[1,3]:=0; end;
 total:=total+2*(a[1,2]+a[2,1]);
 writeln(total);
 close(input); close(output);

end.

来自"http://www.nocow.cn/index.php/USACO/sort3"
个人工具