POJ 3579

题目地址:http://poj.org/problem?id=3579

题目大意

给出$N$个数$$X_1, X_2, \cdots, X_N$$,两两求差$|X_i - X_j|, (1 \leq i < j \leq N)$,可得到$\binom{N}{2}$个差,求出这些差的中位数。

思路

这么大规模考虑二分搜索吧。

C(x)表示以x为中位数是否太小。然后不断二分搜索x值。

C(x)可以这样定义:

  1. 先将X排序
  2. 设 $x\leq X[j] - X[i], j> i$,二分求出所有的$X[j] \geq X[i] + x$的$j$值(可用lower_bound),那么$N-j$表示$\geq x$的个数,累加得cnt。
  3. 判断$cnt \geq \dfrac{\binom{n}{2}}{2}$

AC代码

/*************************************************************************
    > File Name: 3579.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-27 日 11:37:15 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int N;
int CN2 = 0;
int X[100005];

bool C(int x) { // 验证x作为中位数 x = X[j] - X[i] 是否太小
    int cnt = 0;
    for(int i=0; i<N; ++i) {
        cnt += N- (lower_bound(X+i, X+N, X[i]+x) - X); // 统计差值>=x的个数
        // printf("%d\n", lower_bound(X+i, X+N, X[i]+x) - (X));
    }
    // cout << cnt << endl;
    return cnt > CN2>>1;
}

void solve() {
    sort(X, X+N);
    CN2 = N*(N-1) >> 1;
    // C(8);

    int lb = 0, ub = 1000000001;
    while(ub - lb > 1) {
        int mid = (ub + lb) >> 1;
        if(C(mid)) lb = mid; // 中位数过小,半闭半开区间[lb, ub)
        else ub = mid;
    }
    printf("%d\n", lb);
}

int main()
{
#ifdef Oj
    freopen("3579.in", "r", stdin);
#endif
    while(scanf("%d", &N) == 1) {
        for (int i = 0; i < N; ++i) scanf("%d", X+i);
        solve();
    }
    return 0;
}

POJ 3685

题目地址:http://poj.org/problem?id=3685

题目大意

有个$N\times N(1\leq N\leq 50000)$的矩阵$A$,第$i$行和第$j$列上的值$A_{ij}=i^2+100000\times i + j^2 - 100000\times j + i\times j$,问矩阵所有元素从小到大第$M$个元素是多少?

思路

这题坑爆了,需要注意数据规模,特别是$1 \leq M\leq N\times N$,需要64位变量来存。

首先来分析下这个函数$f(i, j) = i^2+100000\times i + j^2 - 100000\times j + i\times j$,

$$\begin{cases}
\dfrac{\partial f(i, j)}{\partial i} = 2 i + j + 100000 > 0\cr
\dfrac{\partial f(i, j)}{\partial j} = 2 j + i - 100000
\end{cases}
$$

可知$f(i,j)$按行递增(同列),而按列不单调(同行)。

C(x)表示矩阵中$<x$的元素有多少个。 所以可以一列一列来求有多少个比x小。然后二分求出正好有$M-1$个数比$x$小即可。

AC代码

/*************************************************************************
    > File Name: 3685.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-27 日 14:28:01 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

const ll MAX = 1e15;
ll T;
ll N, M;
ll f(ll i, ll j) {
    return i*i + 100000*(i-j) + i*j + j*j;
}

bool C(ll x) { // 验证x是否过小。。。。这里写成int x调了好久= =
    ll cnt = 0; // cnt 为<x的个数
    for(int j=1; j<=N; ++j) {
        int lb = 0, ub = N+1; // (lb, ub)
        while(ub - lb > 1) {
            int mid = (lb + ub) >> 1;
            if(f(mid, j) < x) lb = mid; // 半闭半开区间[lb, ub)
            else ub = mid;
         }
        // printf("%d\n", lb);
        cnt += lb;
    }
    // printf("%d\n", cnt);
    return cnt < M;
    // return cnt;
}

void solve() {
    ll lb  = f(0, N), ub = f(N,0)+1;
    while(ub - lb > 1) {
        ll mid = (ub + lb) >> 1;
        // printf("f(%lld)= ", mid);
        if(C(mid)) lb = mid; // 半闭半开区间[lb, ub)
        else ub = mid;
    }
    cout << lb << endl;
}

int main() {
#ifdef Oj
    freopen("3685.in", "r", stdin);
#endif
    cin >> T;
    while (T--) {
        cin >> N >> M;
        solve();
    }
    return 0;
}