虽然归类归到DP里了，但是这道题emmmmm确实没有怎么用dp的思路
题意说给你奇数个数，里面会有一个数出现至少(n+1)/2次，问你这个数是啥
实际上有这个性质很好求，我们只需要统计当前遇到的数，看它出现了几次，一旦遇到别的数出现次数-1，减到1时再遇到别的数就统计这个新的数出现次数，因为出现奇数次，那么所有其他的数都可以与这个特殊数一一抵消最后这个特殊的数还能够保证再出现一次，这样统计一遍即可解决问题
++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int n;
while(~scanf("%d",&n)){
int count=0,number=0;
for(int i=0;i<n;++i){
int tmp;
scanf("%d",&tmp);
if(number!=tmp){
if(count<=1){
number=tmp;
}else{
--count;
}
}else{
++count;
}
}
printf("%d\n",number);
}
return 0;
}
|