傳送門：
Median
思路：
這類型的題目解法都是先確定好答案的上下界之後去二分搜，第Ｋ大表示此數比K-1個數大，仔細思考如何使二分搜最終得到此答案即可。
code:
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
ll N, tar;
vi arr;
void init(){
int tmp;
arr.clear();
for(int i=0;i<N;i++){
tmp = getint();
arr.PB(tmp);
}
tar = (N * (N-1))>>1;
tar = (tar-1)>>1; // 中位數前有幾個數字
}
int l,r,cnt;
inline bool suc(ll p){
l=0, r=0, cnt=0;
while(r+1<N){
if(r<l or arr[r+1] - arr[l] < p)
++r;
else{
cnt += (r-l);
++l;
}
}
cnt += ((r-l+1)*(r-l))>>1;
return cnt<=tar;
}
int sol(){
int L=INT_MAX, R;
sort(arr.begin(), arr.end());
R = arr.back() - arr[0];
for( int i=1;i<N;i++ )
L = min ( L, arr[i] - arr[i-1]);
#define mid ((L+R)/2)
while(R-L>1) suc(mid) ? L=mid : R=mid;
return L;
}
int main(){
while(cin>>N){
init();
cout << sol() << endl;
}
}