USACO/sort3

直接计算

设 cAB 为在A位置上的B的数目，则答案为：

  c21 + c31 + (c21 > c12 ? c23 + c21 - c12 : c32 + c12 - c21)

和后面方法的思路相同。 ...

分析

题意求排序所需的最少移动次数，可以先将输入的数字排序，然后得到不同的地方

比如：

 2 2 1 3 3 3 2 3 1
 1 1 2 2 2 3 3 3 3

用一个组合(a,b)表示应该排序后某个位置应该是a，但之前的是b

则我们得到(1,2), (1,2), (2,1), (2,3), (2,3), (3,2), (3,1)

然后求这些组合能组成的环，结果就是所有环的长度和减去环的个数

 (1,2), (2,1) ---长度为2
 (1,2), (2,3), (3,1) ---长度为3
 (2,3), (3,2) ---长度为2
 结果2+3+2-3=4

(yoer77注：路过，看到上面的算法，觉得有一点需要注意，算法必须保证先消去小环，再消去大环。比如上例中完全可以出现(1,2),(2,3),(3,2),(2,3),(3,1))这样的环。多个小环的代价要小于一个大环。 要解决这个问题，目前我的想法是，把这些数对看成有向图的边，用宽搜每次搜索最短的环，然后减去该环。这样的话应该可以把算法扩展成多值的情况。

补充一点

我们用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。

---

大家思考一下: 要是多个值呢?

另一个简单的思路

我是没看懂前面的(Ciocio注：我也没看懂前面的)...所以自己想了一个 首先 如果两数位置都错了，并且交换后都在正确的位置，这一次交换肯定是必然的 跑一遍 把所有的符合上述条件的数交换回来 每次交换ANS++；

剩下的就是3个数的位置都是错的，也可以通过两次交换达到正确位置 每次交换ans+=2； （其实可以不用交换，就检查一下在1的位置上有多少个不是1的，乘2即可）

一个没有证明的方法

先求出所给数列的最长上升子序列（此题中为6），用数列长度n（9）减去最长子序列长度得到3，说明还有3个数没有放对位置。 如果通过插入的话，答案为3，但题目要求为交换，所以为3+1次交换。

此法只保证过样例，因为对于任意一个数列，通过交换来插入需考虑其他元素的前后位置。 (路过 感觉这个方法是错的，毕竟没法证明是对的，我连样例都过不去。。。)

参考代码

C
C++
pascal
Java

引用

[http://h.thec.cn/starforever/]
 
[http://train.usaco.org/]
{
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;
{貌似少一种对a[1,3]和a[3,1]的处理，方法同上}
   total:=total+2*(a[1,2]+a[2,1]);
  writeln(total);
  close(input); close(output);
end.