[数据结构与算法]Game Prediction acm入门 day3---贪心算法 第四题

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 <= m <= 20) and n (1 <= n <= 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.

题意：m个人打牌，每人n张牌，牌的点数最大不超过n*m且不重复，问最少能赢多少把。

汗，反向被贪心，也就是说，只要这一把场上还有人拥有比你大的牌，你就必输= = 所以思路就是将自己所拥有的牌从大到小排序，每次都打最大牌，每次出牌时先遍历在场所有人的未打出的牌（自己的则事先置1不用遍历），然后只要场上没有比你大的牌就赢，没有就输同时置1表示已被打出。

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

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int p[50];
int mat[1001];
bool cmp(int a, int b)
{
	return a > b;
}
int main()
{
	int n, m;
	int cnt = 1;
	while (scanf("%d %d", &m, &n) != EOF && n && m)
	{
		memset(mat, 0, sizeof(mat));
		memset(p, 0, sizeof(p));
		int max = n * m;
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &p[i]);
			mat[p[i]] = 1;//将自己拥有的牌置1
		}
		sort(p, p + n, cmp);
		int num = 0;
		for (int i = 0; i < n; i++)
		{
			int flag = 0;
			for (int x = p[i]+1; x <= n * m; x++)
			{
				if (mat[x] == 0) {
					flag = 1;//存在更大的牌
					mat[x] = 1;
					break;
				}
				
			}
			if (flag == 0) num++;
		}

		printf("Case %d: %d\n",cnt++, num);
	}
}