Binary Search
給定一堆數字，會有 個差。 問在這些差之中，中位數的值是多少？
先將資料排序，並使用一個 deque ，以 的時間去檢查資料中相差 以內差的數量，是否可以達到不少於中位數的數量。在這裡定義上述結果為 。
之後對該 做二分搜，初始上界為
下界為 -1 ，尋找使得 為真的上界，該上界就是答案。
總體複雜度 。
注意：C++ STL 的 Deque 速度不是很理想，可以自己使用兩個指標實作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <ctime>
#include <stdexcept>
using namespace std;
class solver {
private:
inline int absll(int a) { return a<0?-a:a; }
vector<int> data;
int tar;
inline bool io(void) {
int n;
if(scanf("%d",&n)==EOF) return false;
data.clear();
for(int i=0; i!=n; ++i) {
int t;
scanf("%d",&t);
data.push_back(t);
}
return true;
}
inline void shu(vector<int> &in) {
for(vector<int>::iterator v=in.begin(); v!=in.end(); ++v) {
swap( *v, in.at(rand()%in.size()) );
}
}
inline bool check( int m) {
int counter=0;
deque< int>que;
int i=0;
while (i-que.size()<data.size()) {
for(; i<data.size() && (que.empty()||data.at(i)-que.front() <=m) ; ++i) que.push_back(data.at(i));
if(!que.empty()) que.pop_front();
counter += que.size();
if(counter>=this->tar) return true;
}
return false;
}
int sol() {
sort(data.begin(), data.end());
int ub=*max_element(data.begin(), data.end()) - *min_element(data.begin(), data.end());
int lb=-1;
this->tar = ( ( data.size() * (data.size()-1) )/2 + 1 ) / 2;
while(ub-lb>1) {
int mid=((lb+ub)>>1);
if(check(mid)) {
ub=mid;
}
else lb=mid;
}
return ub;
}
public:
inline void solveit() {
while(io()) {
printf("%d\n",sol());
}
}
solver() {
srand(11);
}
};
int main(void) {
solver sol;
sol.solveit();
return 0;
}