题目链接

Matrix POJ - 3685

思路

$$ 找第k小值的关键在于发现单调性，本题中j确定时函数值关于i单调递增。 $$

时间复杂度

$$ O(Nlog(max(x_{i,j}) - min(x_{i,j}))log(N)) $$

代码

#include <cstdio>

using namespace std;

int n;
long long m;

bool check2(long long i, long long j, long long val) {
    if (i * i + i * 100000 + j * j - j * 100000 + i * j <= val) {
        return true;
    } else {
        return false;
    }
}

bool check(long long val) {
    long long cnt = 0;
    for (int j = 1; j <= n; j++) {
        int l = 1, r = n, ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check2(mid, j, val)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cnt += ans;
    }
    return cnt >= m;
}

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        scanf("%d", &n);// don't forget &
        scanf("%lld", &m);// don't forget &
        long long l = -1e10, r = 1e10, ans = 0;
        while (l <= r) {
            long long mid = (l + r) >> 1;
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}