题目名称	158. [USACO Oct07] 奶牛饮水
输入输出	`privc.in/out`
难度等级	★★
时间限制	1 ms (0.001 s)
内存限制	128 MiB
测试数据	8
题目来源	BYVoid 于2008-10-07加入
开放分组	全部用户
提交状态
分类标签	USACO 贪心
	分享题解

通过：102，提交：199，通过率：51.26%
瑆の時間~無盡輪迴·林蔭	100	0.000 s	0.00 MiB	C++
1020	100	0.000 s	0.00 MiB	C++
lihaoze	100	0.000 s	0.00 MiB	C++
ybh	100	0.001 s	0.11 MiB	Pascal
MayLava	100	0.001 s	0.11 MiB	Pascal
donny	100	0.001 s	0.12 MiB	Pascal
thegy	100	0.001 s	0.12 MiB	Pascal
thegy	100	0.001 s	0.12 MiB	Pascal
thegy	100	0.001 s	0.12 MiB	Pascal
francis	100	0.001 s	0.12 MiB	Pascal

关于奶牛饮水的近10条评论(全部评论)
三值的排序++ cstdio 2013-04-11 14:17 4楼
手僵了。。。减号写加号了。。考试一定要仔细检查 lucifer 2012-10-30 08:04 3楼
11111111 2012-10-11 20:06 2楼
注意细节!!.... zqzas 2008-10-13 21:14 1楼

158. [USACO Oct07] 奶牛饮水

★★ 输入文件：privc.in 输出文件：privc.out 简单对比
时间限制：0.001 s 内存限制：128 MiB

【题目描述】

Farmer John 的$n$头奶牛中，每头奶牛的社会地位取决于她们的产奶量。她们的社会地位被指定为1，2或者3。当他们在井边排队喝水的事后，社会地位最高的(数值最小)的奶牛排在前面。但是奶牛们总是忘掉自己的社会地位，除非Farmer John提醒，所以她们排队很乱。

因此，奶牛们必须通过两两交换位置达到规定的顺序。社会地位为1排在前，2的接着，3排在最后面。奶牛们通常是懒惰的，请你帮助算出所有奶牛一共至少交换几次位置，才能按顺序排列。

【输入格式】

第1行，一个整数$n(1\leq n\leq 1000)$。

第2到第$n+1$行，每行一个整数，为奶牛$i$的社会地位。

【输出格式】

一行一个整数，至少交换的次数。

【输入样例】

【输出样例】

【样例解释】

2   2   2 < 1   1
2 < 1   1   1   1
1 < 2   2   2   2
3   3 < 2   2   2
3   3   3   3 < 2
3   3   3   3   3
2   2 < 3   3   3
3   3   3   3   3
1   1   1 < 2 < 3

【题目来源】

译 by CmYkRgB123