UVa 10142 Australian Voting

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=1083

题意：这个题刘汝佳在挑战编程上翻译的让我各种费解，后来看了这个翻译才明白：http://hi.baidu.com/knowledgetime/blog/item/6017ea04bb35cfc37a894779.html

摘抄如下：

UVa 10142 - Australian Voting
澳大利亚在选举的时候，他们要求投票者在选票上将候选人做一个排名的动作。一开始先计算所有选票中的「第一选择」，如果有某位候选人在此时获得过半(50%)的选票，那么这位候选人立即当选。如果没有任何候选人获得过半的选票，那么票数最少的所有候选人将被排除当选资格，那些原本选择这些候选人的选票，则依照顺位将票投给下一个仍未出局的候选人。这个流程不断的重复(每一次的计票，票数最少的那些候选人都被排除当选)，

或者是所有剩下的候选人得票数相同才停止。

Input

输入的第一列和第一笔测试资料之间，以及连续两笔测试资料之间都包含了一列空白。

输入的第一列有一个整数n (n<=20)代表候选人的个数。接下来的n列每一列依序表示了候选人的名字。这些名字可能长达80个可印出的字元。

然后会有至多1000列，每一列包含了一张选票的内容。每一张选票都包含了一个1~n的排列，第一个数代表这张选票上的「第一选择」，第二个数字代表第二顺位…以此类推。

Output

对于任两笔连续的测试资料中间请输出一列空白。

对每一组测试资料输出赢得选举的候选人名字，或是同时打成平手的所有候选人名字。

Sample Input
1

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

Sample Output
John Doe

这个题只要明确了题意剩下的就比较简单了。

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 const int MAXN = 1010;
  5 
  6 struct vote      //每张选票
  7 {
  8     int who[25];
  9 };
 10 
 11 vote V[MAXN];           //每张选票
 12 char name[25][100];     //候选人名单
 13 bool vis[25];           //记录该候选人是否出局
 14 int count[25];          //每个候选人的票数
 15 int n, k;
 16 
 17 void Solve()
 18 {
 19     memset( vis, true, sizeof(vis) );
 20     int left = 0;
 21 
 22     bool flag = true;             //是否继续统计票数
 23     bool getans = false;          //是否平局
 24 
 25     while ( flag )
 26     {
 27         memset( count, 0, sizeof(count) );
 28         for ( int i = 0; i < k; i++ )
 29         {
 30             for ( int j = 0; j < n; j++ )
 31             {
 32                 int& peo = V[i].who[j];
 33                 if ( vis[ peo - 1 ] )
 34                 {
 35                     ++count[ peo - 1 ];
 36                     break;
 37                 }
 38             }
 39         }
 40 
 41         //   for ( int i = 0; i < n; i++ ) printf( "%d ", count[i] );
 42         //         putchar('\n');
 43 
 44         for ( int i = 0; i < n; i++ )
 45         {
 46             if ( count[i] > k / 2 )          //如果有人票数过半
 47             {
 48                 puts( name[i] );
 49                 flag = false;
 50                 getans = true;
 51                 break;
 52             }
 53         }
 54         if ( !flag ) break;                  //如果有人票数过半，则输出结果，统计结束
 55 
 56         flag = false;
 57         int old;
 58         int i;
 59         left = 0;
 60         for ( i = 0; i < n; i++ )
 61             if ( vis[i] )
 62             {
 63                 old = count[i];
 64                 ++left;
 65                 break;
 66             }
 67         for ( ++i; i < n; i++ )              //判断是否剩下的人票数相同
 68             if ( vis[i] )
 69             {
 70                 ++left;
 71                 if ( count[i] != old )
 72                 {
 73                     flag = true;
 74                     break;
 75                 }
 76             }
 77         if ( !flag || left == 1 ) break;     //如果平局，或者只剩一个候选人，输出结果，退出
 78 
 79         int min = 2000;
 80         for ( int i = 0; i < n; i++ )
 81             if ( vis[i] )                  //少了这个vis，TLE了三遍，进死循环了
 82                 if ( count[i] < min ) min = count[i];
 83 
 84         for ( int i = 0; i < n; i++ )      //每次票数最少的人出局
 85             if ( vis[i] )
 86                 if ( count[i] == min )  vis[i] = false;
 87     }
 88 
 89     if ( !getans )                         //如果平局，输出所有并列的候选人
 90     {
 91         for ( int i = 0; i < n; i++ )
 92             if ( vis[i] ) puts( name[i] );
 93     }
 94 
 95     return;
 96 }
 97 
 98 int main()
 99 {
100     //  freopen( "s.txt", "w", stdout );
101     int T;
102     char str[100];
103     scanf( "%d", &T );
104     while ( T-- )
105     {
106         scanf( "%d", &n );
107         getchar();
108         for ( int i = 0; i < n; i++ )                    //读入候选人名单
109             gets( name[i] );
110 
111         k = 0;
112         while ( gets( str ) != NULL && str[0] != '\0' )  //读入选票
113         {
114             int len = strlen(str);
115             int j = 0;
116             for ( int i = 0; i < len; i++ )
117             {
118                 if ( str[i] != ' ' )
119                 {
120                     int cnt = 0;
121                     while ( str[i] != ' ' && str[i] != '\0' )
122                         cnt = cnt * 10 + ( str[i++] - '0' );
123                     V[k].who[j++] = cnt;
124                 }
125             }
126             ++k;
127         }
128 
129         Solve();
130 
131         if (T) putchar('\n');
132     }
133     return 0;
134 }