码农场
双重二分搜索：对列数X计算∣Xi – Xj∣组成新数列的中位数。
3.1不光是查找值！“二分搜索”
查找第k大的值
对X排序后，与X_i的差大于mid（也就是某个数大于X_i + mid）的那些数的个数如果小于N / 2的话，说明mid太大了。以此为条件进行第一重二分搜索，第二重二分搜索是对X的搜索，直接用lower_bound实现。
#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
#define MAX_N 100000 + 16
ULL N;
ULL C_N_2;
int X[MAX_N];
// mid作为中位数是否太大
bool C(const int& mid)
{
ULL bigger_count = 0;
for (int i = 0; i < N; ++i)
{
bigger_count += X + N - lower_bound(X + i + 1, X + N, mid + X[i]); // 返回大于或等于val的第一个元素位置
}
return bigger_count <= C_N_2 / 2;
}
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
while (cin >> N)
{
for (int i = 0; i < N; ++i)
{
scanf("%d", X + i);
}
sort(X, X + N);
C_N_2 = N * (N - 1) / 2;
ULL lb = 0, ub = *max_element(X, X + N) - *min_element(X, X + N) + 1;
while (ub - lb > 1)
{
int mid = (lb + ub) >> 1;
if (C(mid))
{
ub = mid;
}
else
{
lb = mid;
}
}
cout << lb << endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return 0;
}
///////////////////////////End Sub//////////////////////////////////
| 12835934 | hankcs | 3579 | Accepted | 360K | 579MS | C++ | 1190B | 2014-05-04 03:11:35 |
题主，C()那里可以用尺取法来计算小于等于mid的个数 =V= 时间可以少一半
int p = 0;
for(int i = 1; i < N; i++){
for(int j = p; j < i; j++){
if(X[i] – X[j] <= x){
res += i – j;
p = j;
break;
}
}
}
return res;
不好意思，if里的x就是mid
根据题目描述，好像这组数据是过不了的：
2
-1000000000 1000000000
我的AC程序也过不了这组数据，始终不知道如果考虑这组数据的话，怎样才能过掉题目而且还不会TLE。。请问博主有什么好的想法么？？
ub的初始值小了而已，有负数的情况下改成
int lb = 0, ub = *max_element(X, X + N) – *min_element(X, X + N) + 1;
就行了。另外1000000000会溢出，改成ULL就行了。
表示本弱就是这样做的， 然后TLE无数。。T^T，总感觉自己姿势不对。。