Ignatius and the Princess IV(模拟)

发布于 2020-10-03  0 次阅读


题目大意:

Ignatius and the Princess IV
给你一个长度为n的数组,求其中出现了( n + 1 ) / 2 次的数字

思路:

因为数字出现了( n + 1 ) / 2 ,所以我们可以直接用个res标记与目前假设的数字相同的个数,因为其占比超过一半,所以最后假设的数字必定为答案

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
// #define TDS_ACM_LOCAL
const int N=1e7 +9;
int n;
int a[N];
void solve(){
    while(cin>>n){
        int flag, res;
        res=flag=0;
        for(int i=1; i<=n; i++){
            cin>>a[i];
            if(res<=0) flag=a[i];

            if(a[i]==flag)  res++;
            else            res--;
        }
        cout<<flag<<endl;
    }
    return ;
}

signed main(){
// 	ios::sync_with_stdio(0);
// 	cin.tie(0), cout.tie(0);
// #ifdef TDS_ACM_LOCAL
//     freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
//     freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
// #endif
    solve();
    return 0;
}

平平无奇的大学在读本科生