TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1802
  • 题目
  • P1802【USACO2.1.3】Sorting a Three-Valued Sequence三值的排序IOI96
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排成升序的。
    写一个程序计算出,给定的一个1,2,3组成的数字序列,排成升序所需的最少交换次数。

    输入格式

    第一行:
    奖牌个数N (1 <= N <= 1000)
    第 2行到第N+1行:
    每行一个数字,表示奖牌。共N行。(1..3)

    输出格式

    共一行,一个数字。表示排成升序所需的最少交换次数。

    样例输入

    9
    2
    2
    1
    3
    3
    3
    2
    3
    1

    样例输出

    4