P3680 找妹子
时间: 1000ms / 空间: 1200KiB / Java类名: Main
背景
本题由 @fjzzq2002 提供，已奖励20金币。
描述
sps是zzq的好伙伴。
sps一天叫来了许多个妹子。然后sps看了看这些妹子，说了m个数。这m个数中出现次数最多的数就是sps最喜欢的妹子的编号。因为sps非常专一，他最喜欢的妹子的编号出现的次数大于m的一半。
你自然想知道一下sps最喜欢哪个妹子。
m<=1000000。m个数均在int范围内的正数。
注意看时空限制！
输入格式
第一行一个数m。
第二行m个数。
输出格式
输出出现次数最多的数。
备注
空间1.2MB，连m个数都存不下。
样例输入：
8 2 3 3 2 3 3 2 3
样例输出：
3
【分析】 解题思路如下：
根据题目的规定，出现最多的数出现次数一定是总数的一半以上。在这里我用tmp记录当前的答案，用t来表示当前答案从记录的地方开始比不是这个答案的多的个数。
这样说可能比较难懂。但是下面我们来模拟一组数据，以样例为例：
8
2 3 3 2 3 3 2 3
首先我们读入样例的总数n=8，然后读入第一个数据2.下面我们暂且把2号妹子当做答案的妹子。那么现在我们就相当于从第一个数开始选择到第一个数，现在这些数中和所选的妹子相同的（即2）有一个，不同的有0个，我们就把t赋值为1。
接下来，我们读入第二个数3，这时不同的妹子数就为1了，于是我们将t自减，变为0。
再然后，我们读入第三个数3，不同妹子数变为2，再自减t，变为-1。这时，我们就决定不选择该妹子，而选择我们读入的妹子3记为tmp，将t清空重新计算。
之后一直这样计算，就能得到最后的答案。
不严密的证明：即证明对于一组数其中的一个数，总有从其中的一个数字相同的点出发会在后面的判断中始终不改变tmp，且第一个tmp一定是最终的答案。
∵这个数的出现次数大于总次数的一半
我们假设这个最终的答案出现在一个位置。并且在之后会因为不同的妹子太多被覆盖。
那么，不同的妹子数一定大于这个最终的答案数。
∴在下一次这个数出现时，这个数的剩余总个数一定仍然超过剩余数的总个数的一半。
∴以此类推，最终能够得到答案
【代码】
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; int n; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { int i,j,t=1; n=read(); int tmp=read(); fo(i,2,n) { j=read(); if(tmp==j) t++; else t--; if(t<0) tmp=j,t=1; } printf("%d\n",tmp); return 0; }