USACO 2.1 Sorting A Three-Valued Sequence

深藏阁楼爱情的钟 2022-01-09 04:23 149阅读 0赞

Type: tricky

题目描述：

Sorting a Three-Valued Sequence

Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which 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, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence 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 minimal number of exchange operations that are necessary to make the sequence sorted.

Sorting a Three-Valued Sequence

### INPUT FORMAT ###

<table> 
 <tbody> 
  <tr> 
   <td>Line 1: </td> 
   <td>N (1 &lt;= N &lt;= 1000), the number of records to be sorted</td> 
  </tr> 
  <tr> 
   <td>Lines 2-N+1: </td> 
   <td>A single integer from the set {1, 2, 3}</td> 
  </tr> 
 </tbody> 
</table>

### SAMPLE INPUT (file sort3.in) ###

9221333231

### OUTPUT FORMAT ###

A single line containing the number of exchanges required

### SAMPLE OUTPUT (file sort3.out) ###

思路：

对输入数列的两个copy扫描三遍；

第一遍，找出相同的，标记；

第二遍，对于不同的，找出能跟它配对的，比如：1->2, 2->1。 cnt ++;

第三遍，找出还没有标记过的，剩下的为三元对，1->2, 2->3, 3->1。 cnt +=2；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 代码

/\*   
ID: superbi1  
LANG: C  
TASK: sort3  
 \*/   
\#include  < stdio.h >   
\#include  < string .h >   
\#include  < stdlib.h >   
 \#define  NL 1001   
  
 struct  A \{  
 int  t;  
\};  
 struct  A a1\[NL\], a2\[NL\];  
 int  flg\[NL\];  
  
 int  cmp( const  void  \* a,  const  void  \* b)  
\{  
 return  (( struct  A  \* )a) \-> t  \-  (( struct  A  \* )b) \-> t;  
\}  
  
 int  main()  
\{  
FILE  \* in  =  fopen( " sort3.in " ,  " r " );  
FILE  \* out  =  fopen( " sort3.out " ,  " w " );  
 int  n, i, j;  
 int  cnt  =  0 , t;  
fscanf( in ,  " %d " ,  & n);  
 for  (i = 0 ; i < n; i \++ ) \{  
fscanf( in ,  " %d " ,  & a1\[i\].t);  
a2\[i\].t  =  a1\[i\].t;  
\}  
qsort(a1, n,  sizeof (a1\[ 0 \]), cmp);  
memset(flg,  0 ,  sizeof (flg));  
 for  (i = 0 ; i < n; i \++ ) \{  
 if  (a1\[i\].t  ==  a2\[i\].t) flg\[i\]  =  1 ;  
\}  
 for  (i = 0 ; i < n; i \++ ) \{  
 if  ( ! flg\[i\]) \{  
 for  (j = i \+ 1 ; j < n; j \++ ) \{  
 if  ( ! flg\[j\]  &&  a1\[i\].t  ==  a2\[j\].t  &&  a1\[j\].t  ==  a2\[i\].t) \{  
cnt \++ ;  
flg\[i\]  =  1 ;  
flg\[j\]  =  1 ;  
 break ;  
\}  
\}  
\}  
\}  
t  =  0 ;  
 for  (i = 0 ; i < n; i \++ ) \{  
 if  ( ! flg\[i\]) \{ printf( " %d %d\\n " , a1\[i\].t, a2\[i\].t), t \++ ; \}  
\}  
 if  (t  >  0 ) cnt  \+=  t / 3 \* 2 ;  
fprintf( out ,  " %d\\n " , cnt);  
 return  0 ;  
\}

转载于:https://www.cnblogs.com/superbin/archive/2010/06/01/1749484.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/5842864da6b244ee8f67d07a2fc15d19.png