POJ 1323 Game Prediction

http://poj.org/problem?id=1323

Suppose there are M people, including you, playing a special card game. At the beginning, each player receives N cards. The pip of a card is a positive integer which is at most N*M. And there are no two cards with the same pip. During a round, each player chooses one card to compare with others. The player whose card with the biggest pip wins the round, and then the next round begins. After N rounds, when all the cards of each player have been chosen, the player who has won the most rounds is the winner of the game.

Given your cards received at the beginning, write a program to tell the maximal number of rounds that you may at least win during the whole game. 

Input

The input consists of several test cases. The first line of each case contains two integers m (2?20) and n (1?50), representing the number of players and the number of cards each player receives at the beginning of the game, respectively. This followed by a line with n positive integers, representing the pips of cards you received at the beginning. Then a blank line follows to separate the cases.

The input is terminated by a line with two zeros. 

Output

For each test case, output a line consisting of the test case number followed by the number of rounds you will at least win during the game.

Sample Input

2 5
1 7 2 10 9

6 11
62 63 54 66 65 61 57 56 50 53 48

0 0

Sample Output

Case 1: 2
Case 2: 4

http://blog.csdn.net/angelniu1024/article/details/49152861

题目大意：m个人（包括你）玩一个卡片游戏，每个人n张卡片，卡片上数字为小于等于n * m的正整数，没有重复的数字。每轮比赛，每个人拿出一张牌，卡片上数值最大的那个人获得本轮胜利。输入m、n，接着输入你获得的每张卡片上的数字，接着输入一个空行，求你最少可以获得几次胜利。

题目解析：由于m，n较小，可以依次枚举你的每张卡片上的数值，找到一张在别人手里的牌，这个牌的数值最接近且大于它，并标记为使用过，若找不到，则证明你可以凭借本张牌在一轮比赛中获胜。

const int MAXN = 100010;
int card[MAXN];
bool flag[MAXN];
int main() {
    int m, n;
    int nIndex = 1;
    while (cin >> m >> n && m && n) {
        memset(flag, 0, sizeof(flag));
        for (int i = 1; i <= n; i++) {
            cin >> card[i];
            flag[card[i]] = true;
        }
        getchar();getchar();
        int ans = 0;
        for (int i = 1; i <= n; i++)  {
            bool isGreat = false;
            for (int j = 1; j <= n * m; j++) {
                if (!flag[j]) {
                    if (j > card[i]) {
                        isGreat = true;
                        flag[j] = true;
                        break;
                    }
                }
            }
            if (!isGreat) {
                ans ++;
            }
        }
        cout << "Case " << nIndex << ": " << ans << endl;
        nIndex ++;
    }
    return 0;
}

http://java-mans.iteye.com/blog/1647994
先将手上的牌排序，然后从小到大扫描，如果存在比当前数大且未标记的数，则输的轮数++。

1. int main()  
2. {  
3.     int i,j,count=1;  
4.     while(scanf("%d%d",&m,&n),m|n)  
5.     {  
6.         memset(flag,0,sizeof(flag));  
7.         for(i=0;i<n;i++)  
8.         {  
9.             scanf("%d",&a[i]);  
10.             flag[a[i]]=1;  
11.         }  
12.         sort(a,a+n);  
13.         ans=0;  
14.         for(i=0;i<n;i++)  
15.         {  
16.             for(j=a[i]+1;j<=n*m;j++)  
17.             {  
18.                 if(!flag[j])  
19.                 {  
20.                     flag[j]=1;  
21.                     ans++;  
22.                     break;  
23.                 }  
24.             }  
25.         }  
26.         printf("Case %d: %d\n",count++,n-ans);  
27.     }  
28. } 

https://xuanwo.org/2014/08/12/POJ-1323-Game-Prediction/
https://asanchina.wordpress.com/2016/01/02/1323-game-prediction/