首页 > ACM题库 > HDU-杭电 > HDU 1338 Game Prediction-贪心-[解题报告] C++
2013
12-09

HDU 1338 Game Prediction-贪心-[解题报告] C++

Game Prediction

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2 5
1 7 2 10 9

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

0 0

样例输出:

Case 1: 2
Case 2: 4

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1338

题目意思:

有m个人,每个人有n张牌,牌点为在1~n*m中的不同的数。每回合每个人出一张牌,点数最大的那个人赢,给出A人初始时的n张牌的牌点,问A至少赢的次数。

解题思路:

其他人要想赢得最多,肯定赢A中牌点小的容易,而只要有一个人的牌点大于A牌点就行,此时可以把小牌都出掉。

所以先按A的牌点排序,依次找到大于A的牌点的最小的没出的牌点,然后在出掉较小的m-2张牌。如果连A中较小的牌点都不能赢,后面的肯定不能赢。

这样就达到了,赢得最实算。这就是本题的贪心思想。

代码:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int my[60];
bool vis[1100];

int main()
{
   int n,m,ca=0;

   while(scanf("%d%d",&m,&n)&&m+n)
   {
      memset(vis,false,sizeof(vis));
      for(int i=1;i<=n;i++)
      {
         scanf("%d",&my[i]);
         vis[my[i]]=true;
      }
      sort(my+1,my+n+1); //按自己手上的牌,从大到小排序
      //如果其他人能赢,则只要有一张牌超过自己手上牌就行了,这时可以丢掉其他的小牌
      //当没有比自己大的牌时,后面的一定自己赢了
      int pos=1,ans=0;
      for(int i=1;i<=n;i++)
      {
         int tt=my[i],j;
         for(j=tt+1;j<=n*m;j++) //找到一张没出的比自己最靠近的大牌
            if(!vis[j])
            {
               vis[j]=true;
               break;
            }
         if(j>n*m) //找不到后面肯定自己赢
         {
            ans=n-i+1;
            break;
         }
        if(m==2) //其他人已经出完了
           continue;
        for(int k=0;;) //其他人出较小的牌
        {
           if(!vis[pos])
           {
              vis[pos]=true;
              k++;
           }
           pos++;
           if(k>=m-2)
              break;
        }
      }
      printf("Case %d: %d\n",++ca,ans);

   }
   return 0;
}

解题报告转自:http://blog.csdn.net/cc_again/article/details/9492605


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1