小弟愚笨，时空间复杂度和英文都不懂，不过根据问题描述想出一个办法，不过我还没能写出代码，等下去试试

我的想法如下：

因为数据只有{1,2,3}3种可能
那么分别统计出1和2的数量
例如{2,2,1,3,3,3,2,3,1}
1有两个，2有三个。

然后进入交换环节
for(i=0; i < i1_Count; i++)
{
    if (arr[i] == 1)
        countinue;
    else
        for(j=i1_Count - 1; j < iCount; j++)
        {
            if( arr[j] == 1)
            {
                swap(arr[i],arr[j]);
                iChangeCount++;   //这么一小段过程我按了无数次Ctrl+S在网页上.....
                break;
            }
        }
}

2的过程也如此类推

好吧我的语文也不行

我的想法其实是
排序后，有多少个1前几位就是1..有多少个2,那么1之后的几位也都是2，然后因为1和2都排好了那么3肯定也是全在后面了。根据这个想法那么应该就比较容易写出最小交换次数了(我想......





BTW:妹子待遇无限好


[ 本帖最后由 随风飘荡 于 2012-7-22 15:18 编辑 ]

我靠，我来试试这样可不可以。

统计1,2,3分别有多少个，若1最多，比如说为n个，那么我们排列2,3，假设2有m个，3有t个。

2的位置从n+1到n+m,3的位置从n+m+1到n+m+t，再去测一遍。

我刚按照我第二种方法写了个代码直接RUNTIME ERROR！

D版大大在妹子的贴子上果然活跃无比，电话拿到了没，我也试试去，刚去洗澡，广州好恐怖，要台风了

我又来了，我不是针对ACM的，不过应该能行哦

output 1
/* -------------------------------
12
3 2 1 3 2 1 3 2 1 1 2 3
1  1  1  1  2  2  2  2  3  3  3  3

 change:5
------------------------------- */
output2 

/* -------------------------------
9
2 2 1 3 3 3 2 3 1
1  1  2  2  2  3  3  3  3

 change:4
------------------------------- */

求指点~


[ 本帖最后由 随风飘荡 于 2012-7-22 16:30 编辑 ]

佩恩估计是哪里存在越界，没看到代码不好说。

而随风，你的第1组输出结果就不对，正确结果是4。

是的，回过头我也看出来了如果分优先级从不同区域查找的话代码会变得无比繁杂，我再想想

在下写的  求指点

错了  第一组 奇怪我们居然是一样5

标题加个色，以示鼓励

终究我还是没想出别的办法，我规避开了这个问题，这次应该能通过

out
/* ----------------------------
12
1 2 3 1 2 3 3 2 1 1 2 3
1  1  1  1  2  2  2  2  3  3  3  3

 change:4

20
1 2 3 3 2 1 1 1 1 2 3 3 2 1 2 3 2 1 2 1
1  1  1  1  1  1  1  1  2  2  2  2  2  2  2  3  3  3  3  3

 change:6

9
2 2 1 3 3 3 2 3 1
1  1  2  2  2  3  3  3  3

 change:4
---------------------------- */

说来论坛在线人数近万每日超不过500贴是什么情况


[ 本帖最后由 随风飘荡 于 2012-7-22 18:40 编辑 ]