文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > USACO代码解析Sorting A Three-Valued Sequence (sort3)
侵权投诉

USACO代码解析Sorting A Three-Valued Sequence (sort3)

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排序。。。下面的就怕:

第1页

你可能喜欢

热门文档

相关文档

  • USACO代码解析Packing Rectangles

    USACO代码解析Packing Rectangles_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Packing Rectangles描述 给定 4 个矩形块,找出一个最小的封闭矩形将这 4 个矩...

  • section2.1.3 Sorting a Three-Valued Sequence

    USACO代码解析Sorting A... 3页 1下载券 A Novel Three-Carbon R... 暂无...SEQUENCE Sorting a Three-Valued Sequence 三值的排序 IOI'96 - Day 2 译 ...

  • USACO代码解析Prime Palindromes (pprime)

    USACO代码解析Prime Palindromes (pprime)_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Prime Palindromes (pprime)描述 因为 151 既是一个质数又是一个回文...

  • USACO代码解析Runaround Numbers (runround)

    USACO代码解析Runaround Numbers (runround)_计算机软件及应用_IT/计算机_专业资料。USACO代码解析Runaround Numbers (runround)描述 循环数是那些不包括 0 且没有...

  • usaco第一章试题

    usaco第一章试题_计算机软件及应用_IT/计算机_专业资料...Sorting A Three-Valued Sequence (sort3) Healthy ...遇颜色变换时再将 b 指定给 a 即可, 代码十分简...

  • USACO代码解析SuperPrime Rib (sprime)

    USACO代码解析SuperPrime Rib (sprime)_计算机软件及应用_IT/计算机_专业资料。USACO代码解析SuperPrime Rib (sprime)描述 农民约翰的母牛总是产生最好的肋骨。 你...

  • USACO代码解析Preface Numbering (preface)

    USACO代码解析Preface Numbering (preface)USACO代码解析Preface Numbering (preface)隐藏>> 描述 一类书的序言是以罗马数字标页码的。 传统罗马数字用单个字母表示特定...

  • USACO代码解析Mother's Milk (milk3)

    USACO代码解析Mother's Milk (milk3)_计算机软件及应用_IT/计算机_专业资料。...(found)); fin >>a >>b >>c; DFS(0,0,c); sort(ans,ans+p+1);...

  • USACO全部译题

    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及代码解析

    USACO题目Friday the Thirteenth及代码解析_计算机软件及应用_IT/计算机_专业资料。USACO题目Friday the Thirteenth及代码解析描述13 号又是一个星期五。13 号在星期...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email