ACM刷题之路（十八）二分 2019暑期集训 POJ 3579 Median

题目链接：传送门

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

1. 4
2. 1 3 2 4
3. 3
4. 1 10 2

Sample Output

1. 1
2. 8

题意：每一组数据给一个n，后面给n个数，求这些数之间的差绝对值的中位数，比如例子1 3 2 4 ，差为1，1，1，2，2，3，如果个数为偶数则取中间前面，奇数取中间的数。

分析：

要求差的中位数，最暴力的就是把所有的差都算出来，再sort排序，然后取中间的数输出，当然肯定超时。

我的做法是用两个二分，第一个二分中位数的值，第二个二分试探这个值的可行性。

比如例子：

4

1 3 2 4

先对它排序  放入vector  然后是1 2 3 4

那么它一定有6个差  计算方法为1 + 2 + 3个差   即(1+n-1)*n/2 == (n-1)*n/2;

差的最小值假设是0，就是二分的起点s = 0 ；差一定大于0

最大值假设是a[n-1]-a[0]+1，也就是二分的终点e = 4；差一定小于最大值和最小值的差

接着先使用一次二分，找可能的中位数的值，日常  while(s<e){}   走起

第一次二分找到mid=(s+e)/2 = 2;

假设有m个差大于要求的3   ：    比如1 2 3 4 5 6这样6个数  题目要求的中位数是第三个数

说明这个mid太小了，答案在mid到e的范围内，所以让s=mid；

否则，答案肯定在s到mid的范围内，让e=mid；

题目第一个例子的第一次二分，mid=2；

那么4-2    4-1   3-1 这三个差要大于等于mid值，即不满足3>3

所以答案在s=0到mid=2的范围内，以此类推，二分下去

最后二分终止时就可以找到正确答案。

但是不明白这题为什么在s=mid;或者e=mid的地方不用加1减1都可以不卡死循环

下面贴我自己手打的代码 464K 688MS

1. #include<iostream>
2. #include<algorithm>
3. #include<cstring>
4. #include<vector>
5. using namespace std;
6. vector<int>v;
7. int xiangshu, n;
8. bool dd(int x) {
9.  int sum = 0;
10.   for (int i = 0; i < n; i++) {
11.     sum += v.end() - lower_bound(v.begin(), v.end(), v[i] + x) ;
12.   }
13.   if (sum > xiangshu) return true;
14.   return false;
15. }
16. int main()
17. {
18.   int num;
19.   while (~scanf_s("%d", &n)) {
20.     v.clear();
21.     for (int i = 0; i < n; i++) {
22.       scanf_s("%d", &num);
23.       v.push_back(num);
24.     }
25.     xiangshu = n * (n - 1) / 2;
26.     if (xiangshu & 1) {
27.       xiangshu = xiangshu / 2;
28.     }
29.     else {
30.       xiangshu /= 2;
31.     }
32.     sort(v.begin(), v.end());
33.     int s = 0, e = v[n - 1] - v[0] + 1;
34.     while (s < e - 1) {
35.       int mid = (s + e) / 2;
36.       if (dd(mid)) {
37.         s = mid ;
38.       }
39.       else {
40.         e = mid;
41.       }
42.     }
43.     printf("%d\n", s);
44.   }
45.   return 0;
46. }