題目：
找出給定遞增序列的衆數，并求出衆數在序列中出現的次數（重數）
思路：
一開始看到題目寫的時候，用的是O(n)級别的一遍掃描法，邊掃描邊統計，現在用分治法來寫一下
對于一個數組，首先我假設中間元素是衆數，并且用區間内掃描法來定位所有與中間數相等的數，區間标記為[p,r]，個數記為midcnt
這樣就通過p,r将區間分成了三段，接下來要做的應該是向[left,p-1]和[r+1,right]分别拓展，看這兩個區間内是否會出現衆數
在拓展的時候我們可以做一個優化，如果某個區間所有的元素個數比中與間元素（目前假設的衆數）相等的數的個數還少，那麼這個區間内不可能出現衆數，可以不用再去找，如果找到的新的數比目前的重數大，則新的衆數誕生。
上代碼：
1 #include<iostream>
2 using namespace std;
3 int a[] = { 1,1,2,2,2,3,3,3,3,3,4,4,5,6,7,7,7 };
4 int len = sizeof(a) / sizeof(a[0]);
5 int num;
6 int cnt=0;
7 void pos(int left, int right,int mid, int &p, int &r) {
8 int i;
9 for (i = left; i <= right; i++) {
10 if (a[i] == a[mid]) {
11 break;
12 }
13 }
14 p = i;//mid的左邊界
15 for (i = p + 1; i <= right; i++) {
16 if (a[i] != a[mid]) {
17 break;
18 }
19 }
20 r = i - 1;//mid的右邊界
21 }
22 void getMaxCnt(int left, int right) {
23 int mid = (left + right) / 2;
24 int p;
25 int r;
26 pos(left, right, mid, p, r);
27 int midcnt = r - p + 1;
28 if (midcnt > cnt) {
29 num = a[mid];
30 cnt = midcnt;
31 }
32 if (p - left > cnt) {
33 getMaxCnt(left, p - 1);
34 }
35 if (right - r - 1 > cnt) {
36 getMaxCnt(r + 1, right);
37 }
38 }
39 int main() {
40 getMaxCnt(0, len - 1);
41 cout << num << endl;
42 cout << cnt << endl;
43
44 return 0;
45 }