题目传送门
Ignatius and the Princess IV
题目大意
给你一个长度为n的数组，求其中出现了
(
n
+
1
)
/
2
(n+1)/2
(n+1)/2次的数字
思路
因为数字出现了
(
n
+
1
)
/
2
(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;
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(){
solve();
return 0;
}
