USACO代码解析Sorting A Three-Valued Sequence (sort3)
描述
排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1,2和
3。我们用交换的方法把他排成升序的。
写一个程序计算出,给定的一个1,2,3组成的数字序列,排成升序所需的最少交换次数。
[编辑]格式
PROGRAM NAME: sort3
INPUT FORMAT:
(file sort3.in)
第一行:
奖牌个数N (1 <= N <= 1000)
第 2行到第N+1行:
每行一个数字,表示奖牌。共N行。(1..3)
OUTPUT FORMAT:
(file sort3.out)
共一行,一个数字。表示排成升序所需的最少交换次数。
[编辑]SAMPLE INPUT
9
2
2
1
3
3
3
2
3
1
[编辑]SAMPLE OUTPUT
4
分析
题意求排序所需的最少移动次数,可以先将输入的数字排序,然后得到不同的地方 比如:
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
这个不怕题目改为1234排序。。。下面的就怕:
USACO代码解析Packing Rectangles_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Packing Rectangles描述 给定 4 个矩形块,找出一个最小的封闭矩形将这 4 个矩...
USACO代码解析Sorting A... 3页 1下载券 A Novel Three-Carbon R... 暂无...SEQUENCE Sorting a Three-Valued Sequence 三值的排序 IOI'96 - Day 2 译 ...
USACO代码解析Prime Palindromes (pprime)_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Prime Palindromes (pprime)描述 因为 151 既是一个质数又是一个回文...
USACO代码解析Runaround Numbers (runround)_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Runaround Numbers (runround)描述 循环数是那些不包括 0 且没有...
usaco第一章试题_计算机软件及应用_IT/计算机_专业资料...Sorting A Three-Valued Sequence (sort3) Healthy ...遇颜色变换时再将 b 指定给 a 即可, 代码十分简...
USACO代码解析SuperPrime Rib (sprime)_计算机软件及应用_IT/计算机_专业资料。USACO代码解析SuperPrime Rib (sprime)描述 农民约翰的母牛总是产生最好的肋骨。 你...
USACO代码解析Preface Numbering (preface)USACO代码解析Preface Numbering (preface)隐藏>> 描述 一类书的序言是以罗马数字标页码的。 传统罗马数字用单个字母表示特定...
USACO代码解析Mother's Milk (milk3)_计算机软件及应用_IT/计算机_专业资料。...(found)); fin >>a >>b >>c; DFS(0,0,c); sort(ans,ans+p+1);...
USACO全部译题_理学_高等教育_教育专区。USACO TRAIN...Sorting a Three-Valued Sequence 2.1.4 Healthy ...9 2 2 1 3 3 3 2 3 1 sort3 N (1 <= ...
USACO题目Friday the Thirteenth及代码解析_计算机软件及应用_IT/计算机_专业资料。USACO题目Friday the Thirteenth及代码解析描述13 号又是一个星期五。13 号在星期...
热门文档