题目大意就是给你n个数(保证n为一个奇数),存在一个数出现的次数大于(n+1)/2次,求这个数;
这个数出现的次数比其他数出现的次数加起来还多,那么当这个数出现时+1,其他的数出现时-1,最后得到的数为正数。
假定一个数为特殊数,若当前数与特殊数相同则cnt++,若不相同则cnt--,如果这时cnt<0,用当前数替代特殊的数。不管怎么样,由于特殊数次数大于(n+1)/2次,最终保留的数一定是特殊数。
代码如下
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
int n;
while(~scanf("%d",&n))
{
int ans,x,cnt = 0;
for(int i = 0;i < n; i++)
{
scanf("%d",&x);
if(ans == x)
++cnt;
else
--cnt;
if(cnt < 0)
{
cnt = 0;
ans = x;
}
}
printf("%d\n",ans);
}
return 0;
}
我还写了一个比较暴力的,居然过了,应该是他们评测的数据有问题,没有太大的数,也一并把代码贴在这里,推荐大家看上面的思路,下面这个的思路我就不说了,大家一看就明白了。
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
int n,a[1000000];
while(~scanf("%d",&n))
{
memset(a,0,sizeof(a));
for(int i = 0;i < n; i++)
{
int x;
scanf("%d",&x);
a[x]++;
}
int maxn = 0,index;
for(int i = 0;i < 1000000; i++)
{
if(maxn < a[i])
{
maxn = a[i];
index = i;
}
}
printf("%d\n",index);
}
return 0;
}
标签:HDU,int,scanf,ans,1029,Ignatius,++,cnt,include From: https://blog.51cto.com/u_16131191/6356098