HDU 5038 Grade

时间:2022-05-26 02:49:33

解题思路:这题最关键的是要读懂题意,If not all the value are the same but the frequencies of them are the same, there is no mode.这句话是至关重要

      的一句。意思是:如果不是所有的值是相同的,并且他们的出现次数是相同的,那么就没有模型。如,1 1 2 2 3 3 ,它们并不是所有的数都是相同的的,

      并且1出现2次,2出现2次,3出现2次,所以这组数据是没有模型的,同理,1 2 3 4 5 也是没有模型的,输出Bad Mushroom.但是,要注意特殊判断,

      如,1 1 1 1 1,它所有的数是相同的,它是有唯一模型的。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = ;
int hash2[maxn], num[maxn], vis[maxn];
int w[maxn], s[maxn];
int main()
{
int t, n, kase = ;
scanf("%d", &t);
while(t --)
{
scanf("%d", &n);
memset(hash2, , sizeof(hash2));
for(int i = ; i < n; i++)
{
scanf("%d", &w[i]);
s[i] = - (-w[i])*(-w[i]);
hash2[s[i]]++; //用哈希标记每个对应的grade出现的次数。
}
printf("Case #%d:\n", kase ++);
int ok = ;
for(int i = ; i < n; i++)
{
if(s[i] != s[]) //判断是否所有的grade是否是相同的。
{
ok = ;
break;
}
}
if(ok == ) //如果所有的grade都相同,则直接输出。
{
printf("%d\n", s[]);
continue; //不要掉了。
}
int max1 = -inf;
for(int i = ; i < n; i++)
{
if(hash2[s[i]] >= max1)
{
max1 = hash2[s[i]]; //找出grade出现次数最大的,可以有多个。
}
}
int cnt = ;
int flag = ;
memset(vis, , sizeof(vis));
for(int i = ; i < n; i++)
{
if(hash2[s[i]] < max1) flag = ; //如果有与出现最大次数不相同次数的数,则
//一定是有输出的。
if(hash2[s[i]] == max1 && !vis[s[i]])
{
vis[s[i]] = ;
num[cnt++] = s[i]; //cnt记录出现了多少个频次最大的,num数组则存下对应的值。
}
}
if(!flag) //如果全部出现频次相同,则是没有模型的。
{
printf("Bad Mushroom\n");
continue;
}
if(cnt == ) printf("%d\n", num[]); //一个直接输出。
if(cnt > )
{
sort(num, num+cnt);
for(int i = ; i < cnt-; i ++) printf("%d ", num[i]);
printf("%d\n", num[cnt-]); //注意输出格式即可。
}
}
return ;
}