首页 > 代码库 > POJ 1323-Game Prediction--贪心

POJ 1323-Game Prediction--贪心

2024-07-17 00:37:53   225人阅读

Game Prediction
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 9552 Accepted: 4566

Description

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

一道简单的贪心，说实话我是看了题解才明白的，sad 我总感觉贪心很难。。

有n个打牌，每人m张牌，牌的编号从1--n*m 然后比大小，谁的牌大谁赢，主要就是记录自己手中的牌的问题，可以设一个数组a，初始化为0，每输入自己手中的一张牌号x，令a[x]=1;以此来代表自己手中的牌，将牌从大到小遍历，如果单前牌是自己手中的牌的牌那么win++；否则win--；（如果是别人的牌那么你这局肯定输了）设一个max变量记录win的最大值就是答案。



#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
bool my[10010];
int main()
{
	int n,m,i,ca=0,x;
	while(cin>>n>>m)
	{
		if(!n&&!m) break;
		memset(my,0,sizeof(my));
		for(i=0;i<m;i++)
		{
			cin>>x;
			my[x]=1;
		}
		int win=0,max=0;
		for(i=m*n;i>0;i--)
		{
			if(my[i])
			{
				win++;
				if(win>max)
					max=win;
			}
			else
				win--;
		}
		cout<<"Case "<<++ca<<": "<<max<<endl;
	}
	return 0;
}


联系
我们