题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1800
这道题目是道哈希的简单题,主要难度在于怎样将问题抽象画。
对于每一组数据,我要求它最少需要几把扫帚。
我们把2 4 5 6 4这组输入排序,变成了2 4 4 5 6,每一次取最长的一个递增序列,取的次数就是我们需要的答案,请仔细想想,若输入为2 4 5 6,那我们只需要一把扫帚就能装下所有人,但我们输入2 4 4 5 6,就需要两把了,我们每次都取了一个递增序列,为什么开始要一把,现在要两把呢?因为我还有一个人的等级也是4,而我已经有一个4而且序列必须递增,所以同样的等级4我只能取一个人。另一个只好留着下次取了。所以这个问题就抽象成了:求一组数中出现频率最大的那个数出现的次数!
这样想是不是很简单了?
每次输入一个数i,数组mp[i]++一次,之后把i的范围全部遍历一遍,把mp数组最大的一个元素输出就行了。(若对stl里面的map不了解可以自己百度一下)
贴个完整的代码:
#include <iostream>
#include <string>
#include <stdio.h>
#include <map>
using namespace std;
int main()
{
int n,max;
map<int,int>mp;
int num;
while(scanf("%d",&n)!=EOF){
mp.clear();
max=0;
while(n--){
scanf("%d",&num);
mp[num]++;
if(mp[num]>max){
max=mp[num];
}
}
printf("%d\n",max);
}
return 0;
}