HDU 1029 Ignatius and the Princess IV(数论)

时间:2024-06-24 16:36:26
#include <bits/stdc++.h>
using namespace std; int main(){
int n;
while(~scanf("%d",&n)){
int x,ans,cnt = 0;
while(n--){
scanf("%d",&x);
if(cnt == 0){
ans = x;
cnt++;
}else{
if(x == ans)
cnt++;
else
cnt--;
}
}
printf("%d\n",ans);
}
return 0;
}
/*

题目要求一个数至少出现(n+1)/2次。用cnt来记录解出现的次数,出现了正确解就令cnt自增1,不是正确解就使cnt自减1。

那么,正确解对应的cnt一定是不小于1的。可以用一个极端的例子来说明下:输入3 3 3 3 3 3 2 1 5 6 8,开始当ans=3时,cnt=6,

那么继续执行num!=3了,cnt开始自减,但最终cnt=1,始终不会进入程序if(cnt==0){}内部执行了。

利用最终的cnt,还可以计算出解出现的次数。*/

  

#include <iostream>
#include <stdlib.h>
using namespace std; int a[1000000]; int cmp(const void * x,const void* y)
{
return (*(int*)x - *(int*)y);
} int main()
{
int n,i,b,j,flag; while(cin >> n)
{
j = b = 0;
for(i = 0;i<n;i++)
{
cin >> a[i];
}
qsort(a,n,sizeof(int),cmp);
flag = a[0];
for(i = 0;i<n;i++)
{
if(a[i] == flag)
b++;
else if(a[i]!=flag)
{
if(b>=(n+1)/2)
{
break;
}
b = 0;
flag = a[i];
}
}
cout << flag << endl;
} return 0;
}

 

#include<stdio.h>
#include<string.h>
int map[500001];
int main()
{
int n,i,a,max;
while(scanf("%d",&n)!=EOF)
{
memset(map,0,sizeof(map));
for(i=0;i<n;i++)
{
scanf("%d",&a);
map[a]++;
if(map[a]>=(n+1)/2)
max=a;
}
printf("%d\n",max);
}
return 0;
}

  

#include <iostream>
#include <cstring>
using namespace std;
int a[1000001];
int main()
{
int x, n, i, num;
while(cin >> n)
{
memset(a, 0, sizeof(a));
for(i = 0; i < n; i++)
{
cin >> x;
a[x]++;
if(a[x] == (n+1)/2)//只要成立肯定是最大的了即保存再输出
num = x;
}
cout << num << endl;
}
return 0;
}

  

多元素即在数列中出现次数多于n/2的元素

我们很容易的看出来,在一个序列中如果去掉2个不同的元素,
那么原序列中的多元素,在新的序列中还是多元素,
因此我们只要按照序列依次扫描,先把t赋值给result,
增加个计数器,cnt = 1;然后向右扫描,
如果跟result相同,则cnt++,不同,那么cnt --,
这个真是我们从上面那个结论里得出的,一旦cnt == 0了,
那么必定c不是多元素,这个时候把t赋值为result,cnt = 1;,
重复该过程,知道结束,这个时候,result就是多元素,
这个的时间复杂度为n,该题本来可以用数组保存每个元素,
然后递归上述过程,可是,用数组超内存,
因此我们可以直接按照上述过程计算