题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1029
就是给你n（n是奇数）个数找出个数大于（n+1）/ 2 的那个数；
n的取值范围是 n(1<=n<=999999)
这是很久之前做的一道题了，当时就是用sort排序，输出a[(n+1)/2]就行了，在这道题上很容易就过了，但是如果说n很大的大到无法开数组呢，所以有搜了一下别人的题解；
我们可以知道结果的那个数的个数一定大于总个数的一半（关键），所以我们可以线性的做，当cnt=0的时候更新ans；否则当当前数为ans的时候让cnt++，不相等时就让cnt--；
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<iostream> using namespace std; #define N 1000000 int main() { int n, num, cnt, ans; while(scanf("%d", &n)!=EOF) { cnt = 0; for(int i=0; i<n; i++) { scanf("%d", &num); if(cnt==0) ans = num, cnt++; else { if(num==ans) cnt++; else cnt--; } } printf("%d\n", ans); } return 0; }
排序的（n*log(n)）：
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<iostream> using namespace std; #define N 1000000 int a[N]; int main() { int n; while(scanf("%d", &n)!=EOF) { for(int i=0; i<n; i++) scanf("%d", &a[i]); sort(a, a+n); printf("%d\n", a[(n+1)/2]); } return 0; }
Ignatius and the Princess IV---hdu1029（动态规划或者sort）
原文：http://www.cnblogs.com/zhengguiping--9876/p/4906664.html
