HDU 1029 Ignatius and the Princess IV（數論）

#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，該題本來可以用數組儲存每個元素，
然後遞歸上述過程，可是，用數組超記憶體，
是以我們可以直接按照上述過程計算