hdu 1029 求出现次数过半的数

已知必定存在一个元素出现次数超过一半，考虑用栈

若当前元素等于栈顶元素，入栈，反之出栈，并将当前元素入栈

最终的栈顶元素即是所求

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define rep(i,a,b) for(int i=(a);i<=(b);++i)

#define per(i,a,b) for(int i = (a);i>=(b);--i)

#define fo(i,a,b) for(int i =(a);i<(b);++i)

#define de(x) cout<<#x<<" = "<<x<<endl;

#define endl '\n'

#define ls(p) ((p)<<1)

#define rs(p) (((p)<<1)|1)

using namespace std;

typedef long long ll;

const int mn = 1e6+10;

int n;

ll Top,t;

int cnt;

// stack

int main(){

	while(scanf("%d",&n)!=EOF){

		cnt = 1;

		scanf("%lld",&Top);

		rep(i,2,n){

			scanf("%lld",&t);

			if(t == Top)++cnt;

			else{

				if(cnt == 1)

					Top = t;

				else{

					--cnt;

				}

			}

		}

		printf("%lld\n",Top);

	}

}

巴特西

hdu 1029 求出现次数过半的数

最新文章

热门文章