CodeVS4419FFF团的菊花
CodeVs4419 FFF团卧底的菊花
时间限制:2s 空间限制64.0MB
题目描述 Description
FFF 团卧底在这次出题后就知道他的菊花可能有巨大的危险,于是他提前摆布好了菊花阵,现在菊花阵里有若干朵菊花,出现次数最多的那一朵就是出题人的,你的任务是需要找出出题人的菊花。
输入描述 Input Description第一行为 n
第二行为 n 朵菊花
输出描述 Output Description一行,为出题人的菊花
样例输入 Sample Input5
1 1 1 2 3
样例输出 Sample Output1
数据范围及提示 Data Size & Hint对于 100%的数据,n<=5000000,每个数都在 int 范围内,保证出题人的菊花出现的次数大于等于[n/2]
真是一道 水题啊，我花了一个半小时才做出来。幸运的是AC了。刚刚看到这道题的时候惊呆了，怎么把这么弱的题放在第三题。可是等了一会同学让我刷新网页才发现，内存竟然成了32MB，我再一次惊呆了。等我静下来思考才发现，改内存限制并没有改变它是 水题这个事实。把CodeVs上我的题解搬过来：
如果一个数的出现次数大于N/2，则它的前五位的出现次数也一定是大于N/2，后五位的出现次数也大于N/2，而且都是唯一大于N/2的，所以找出出现次数最多的前五位数、后五位数，拼起来就是解。因为可能有负数，所以可以先把读入的数加上2147483648，再进行处理，最后别忘了减去2147483648 #include#include #include #define inf 0x7fffffffusing namespace std;int a[600050], b[600050];int main() {long long i, x, t, N=0, _N, maxi, maxx;getnum(N);for(i=1;i<=N;i++){x=0;scanf("%lld",&x);x+=inf;x++;a[x%100000]++;b[x/100000]++;}for(i=1;i<=99999;i++){if(a[i]>=N/2 && a[i]<=N){t=i;break;}}for(i=1;i<=99999;i++){if(b[i]>=N/2 && b[i]<=N){t=i*100000+t;break;}}t=t-inf;t--;printf("%lld\n",t);return 0; }
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！