D. K-th nearest

题意概况

给定N个点a1,a2,a3....an,有Q次询问, 每次询问给定 bi 和 ki, 问所有a点中距离 bi 最近第 ki 个点和 bi 的距离是多少

思路

每次暴力去求显然复杂度会爆的。但是有一个发现：第K近的点，那距离也是第K小的

假如最后的答案是ans, 随便选一个点和bi是第m近，距离为dis,如果 m < k, 那么dis < ans, 如果m > k,那么 dis > ans 所以我们可以二分答案

代码如下

#include <bits/stdc++.h>
#define endl '\n';
//#define int long long
using ld = long double;
using lli = long long;
using ull = unsigned long long;
// 二分答案
// 距离b最近的第K个点，肯定是在b的两边找
// 到b点的距离满足单调性，所以可以二分答案
// 距离多时点会多
// 距离少时点会少
// 所以满足单调性
void solve()
{
    int N = 0, Q = 0;
    std::cin >> N >> Q;
    std::vector<int> a(N), b(Q), k(Q);
    for (int i = 0; i < N; i++)
    {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    for (int i = 0; i < Q; i++)
    {
        std::cin >> b[i] >> k[i];
    }
    for (int i = 0; i < Q; i++)
    {
        int lower = 0, high = 2e8;
        while(lower < high)
        {
            int mid = (lower + high) / 2;
            int left = b[i] - mid, right = b[i] + mid;
            int cnt = std::upper_bound(a.begin(), a.end(), right) - std::lower_bound(a.begin(), a.end(), left);
            if (cnt >= k[i])
            {
                high = mid;
            }
            else
            {
                lower = mid + 1;
            }
        }
        std::cout << lower << endl;
    }
}   

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 1;
    //std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

时间复杂度分析

O(Qloglog)