首页 > 动态规划 > 线性DP > hdu 1347 Grandpa is Famous-动态规划-[解题报告]
2013
12-09

hdu 1347 Grandpa is Famous-动态规划-[解题报告]

Grandpa is Famous

问题描述 :

The whole family was excited by the news. Everyone knew grandpa had been an extremely good bridge player for decades, but when it was announced he would be in the Guinness Book of World Records as the most successful bridge player ever, whow, that was astonishing!

The International Bridge Association (IBA) has maintained, for several years, a weekly rank? ing of the best players in the world. Considering that each appearance in a weekly ranking constitutes a point for the player, grandpa was nominated the best player ever because he got the highest number of points.

Having many friends who were also competing against him, grandpa is extremely curious to know which player(s) took the second place. Since the IBA rankings are now available in the internet he turned to you for help. He needs a program which, when given a list of weekly rankings, finds out which player(s) got the second place according to the number of points.

输入:

The input contains several test cases. Players are identified by integers from 1 to 10000. The first line of a test case contains two integers N and M indicating respectively the number of rankings available (2 <= N <= 500) and the number of players in each ranking (2 <= M <= 500). Each of the next N lines contains the description of one weekly ranking. Each description is composed by a sequence of M integers, separated by a blank space, identifying the players who figured in that weekly ranking. You can assume that:

1. in each test case there is exactly one best player and at least one second best player,
2. each weekly ranking consists of M distinct player identifiers.

The end of input is indicated by N = M = 0.

输出:

For each test case in the input your program must produce one line of output, containing the identification number of the player who is second best in number of appearances in the rankings. If there is a tie for second best, print the identification numbers of all second best players in increasing order. Each identification number produced must be followed by a blank space.

样例输入:

4 5
20 33 25 32 99
32 86 99 25 10
20 99 10 33 86
19 33 74 99 32
3 6
2 34 67 36 79 93
100 38 21 76 91 85
32 23 85 31 88 1
0 0

样例输出:

32 33
1 2 21 23 31 32 34 36 38 67 76 79 88 91 93 100

题目大意:爷爷是大神,现在大神要入吉尼斯,但是有人和大神竞争啊,大神想知道有谁和他竞争。

输入N*M,N就是N次比赛,M是个人成绩,也是个人身份。

N次比赛中出现次数最多的就是大神,要输出出现次数仅此于大神的所有人。

解法:明白题意很好做,水题一道,一个sort就解决了

//Memory: 200 KB		
//Time: 204 MS
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct play
{
	int num;
	int s;
};
bool cmp(play a,play b)
{
	if(a.s==b.s)
		return a.num<b.num;
	else
		return a.s>b.s;
}
int main()
{
	int n,m,i,j;
	while(~scanf("%d%d",&n,&m))
	{
		play p[10003];
		memset(p,0,sizeof(p));
		int temp;
		if(n==0 && m==0)
			break;
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
			{
				scanf("%d",&temp);
				p[temp].num=temp;
				p[temp].s++;
			}
		sort(p,p+10000,cmp);
		i=1;
		while(p[i].s==p[i+1].s)
		{
			printf("%d ",p[i].num);
			i++;
		}
		printf("%d\n",p[i].num);
	}
	return 0;
}

解题转自:http://blog.csdn.net/winkloud/article/details/7842755


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧