Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Problem 1: Sorting a Three-Valued Sequence
发信站: 哈工大紫丁香 (2002年03月29日13:55:10 星期五), 站内信件

Problem 1: Sorting a Three-Valued Sequence
Sorting is one of the most frequently done computational tasks. Consider the
 special sorting problem, where the records to be sorted have at most three 
different key values. This happens for instance when we sort medalists of a 
competition according to medal value, that is, gold medalists come first, fo
llowed by silver , and bronze medalists come last.
In this task the possible key values are the integers 1, 2 and 3. The requir
ed sorting order is non-decreasing. Sorting has to be accomplished by a sequ
ence of exchange operations. An exchange operation, defined by two position 
numbers p and q, exchanges the elements in positions p and q.
You are given a sequence of key values. Write a program that computes the mi
nimal number of exchange operations that are necessary to make the sequence 
sorted. (Subtask A). Moreover, construct a sequence of exchange operations f
or the respective sorting (Subtask B).
　
Input Data
The first line of file INPUT.TXT contains the number of records N (1<=N<=100
0). Each of the following N lines contains a key value.
　
Output Data
Write on the first line of file OUTPUT.TXT the minimal number L of exchange 
operations needed to make the sequence sorted (Subtask A). The following L l
ines give the respective sequence of the exchange operations in the order pe
rformed. Each line contains one exchange operation described by two numbers 
p and q, the positions of the two elements to be exchanged (Subtask B). Posi
tions are denoted by the numbers from 1 to N.
　
Example Input and Output
Figure 1 gives an input file and a corresponding output file.
----------------------------------------------------------------------------
----
INPUT.TXT          OUTPUT.TXT
9                  4
2                  1 3
2                  4 7
1                  9 2
3                  5 9
3
3
2
3
1
----------------------------------------------------------------------------
----
Figure 1

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]