题目
\(n\)个数\(a_{1\ldots n}\),两两做差(大减小),得到数组\(b\),求\(b\)的中位数.
思路
对原数组排序,二分枚举中位数\(mid\),求有多少个做差数组中比\(mid\)大/小的数分别由多少个,时间复杂度是\(O(n\log^2n)\),可以卡过去.
正解是双指针?
代码
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
int read() {
int re = 0;
char c = getchar();
bool negt = false;
while(c < '0' || c > '9')negt |= (c == '-') , c = getchar();
while(c >= '0' && c <= '9')re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return negt ? -re : re;
}
const int N = 2e5 + 10;
int abs_(int a) {
return a < 0 ? -a : a;
}
int n , m;
int a[N];
vector <int> ans;
int check(int val) { //return 0(too small) 1(too big) 2(find answer)
int sm = 0 , bg = 0;
int v , l , r;
for(int i = 1 ; i <= n ; ++i) {
v = a[i] + val;
l = lower_bound(a + 1 , a + n + 1 , v) - a , r = upper_bound(a + 1 , a + n + 1 , v) - a;
if(a[l] >= v || l == n + 1)--l;
sm += max(0ll , l - i) ;
bg += n - r + 1;
}
int equ = m - sm - bg;
if(sm >= (m + 1) / 2)return 1;
if(sm + equ < (m + 1) / 2)return 0;
if(equ == 0)return 0;
ans.push_back(val);
return 2;
}
int check2(int val) { //return 0(too small) 1(too big) 2(find answer)
int sm = 0 , bg = 0;
int v , l , r;
for(int i = 1 ; i <= n ; ++i) {
v = a[i] + val;
l = lower_bound(a + 1 , a + n + 1 , v) - a , r = upper_bound(a + 1 , a + n + 1 , v) - a;
if(a[l] >= v || l == n + 1)--l;
sm += max(0ll , l - i) ;
bg += n - r + 1;
}
int equ = m - sm - bg;
if(sm >= m / 2 + 1)return 1;
if(sm + equ < m / 2 + 1)return 0;
if(equ == 0)return 0;
ans.push_back(val);
return 2;
}
signed main() {
// freopen("mid.in" , "r" , stdin);
// freopen("mid.out" , "w" , stdout);
n = read() , m = n * (n - 1) / 2;
for(int i = 1 ; i <= n ; i++)
a[i] = read();
sort(a + 1 , a + n + 1);
int l = 0 , r = 1ll << 31;
while(l <= r) {
int mid = (l + r) / 2;
int tmp = check(mid);
if(tmp == 2)break;
if(tmp == 0)l = mid + 1;
else r = mid - 1;
}
if((m & 1) == 0) {//有两个中位数
l = 0 , r = 1ll << 31;
while(l <= r) {
int mid = (l + r) / 2;
int tmp = check2(mid);
if(tmp == 2)break;
if(tmp == 0)l = mid + 1;
else r = mid - 1;
}
}
int sum = 0;
for(int i : ans)
sum += i;
cout << sum / ans.size();
return 0;
}