[POJ 3579] Median【二分答案】
Problem:
| Time Limit: 1000MS | Memory Limit: 65536K |
Description
Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!
Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.
Input
The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, ... , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )
Output
For each test case, output the median in a separate line.
Sample Input
4 1 3 2 4 3 1 10 2
Sample Output
1 8
Source
Solution:
首先将 X[] 排序，然后在区间[0, X[n] - X[1]]上二分差值即可。
check 时利用 X[] 的单调性，使用哨兵 i, j 维护小于等于当前差值的区间，复杂度为 O(n)。
Code: O(Tnlogn) [296K, 329MS]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int N, X[100005], medianId;
inline bool check(const int &val){
int cnt = 0;
for(register int i = 1, j = 1; i <= N; i++){
while(j < N && X[j + 1] - X[i] <= val) j++;
// Maintain the region where differences are smaller than val
cnt += j - i;
}
return cnt >= medianId;
}
int main(){
while(scanf("%d", &N) != EOF){ // Read this way without terminator
medianId = (N * (N - 1) >> 1) + 1 >> 1; // Beware of the order of median
for(register int i = 1; i <= N; i++) scanf("%d", X + i);
sort(X + 1, X + N + 1);
int lft = 0, rt = X[N] - X[1];
while(lft < rt){
int mid = lft + rt >> 1;
if(check(mid)) rt = mid;
else lft = mid + 1;
}
printf("%d\n", lft);
}
return 0;
}
发表评论