题解

题面描述

给定一个超大智能汽车测试场，有 $n$ 个充电桩，每个充电桩的位置由二维平面坐标 $(x,y)$ 表示。给定智能汽车的当前位置 $(car_x, car_y)$，请设计一个高效的算法，找出距离（行驶距离）最近的 $k$ 个充电桩，并输出相关充电桩信息：编号、坐标、行驶距离。结果按行驶距离升序排序，若距离相等则按编号从小到大排序。行驶距离的计算方法为：

当 $k=0$ 或 $k>n$ 时，输出字符串 null。

思路

1. 边界条件：如果 $k = 0$ 或 $k > n$，直接输出 null。
2. 距离计算：对每个充电桩 $i$，计算$$d_i = |car_x - x_i| + |car_y - y_i|$$
3. 维护前 $k$ 个最小距离：当 $n$ 很大时，不能对所有点全排序。可以使用大小为 $k$ 的最大堆（优先队列）来维护当前最小的 $k$ 个元素：
   • 遍历所有充电桩，计算 $d_i$。
   • 将三元组 $(d_i, i, x_i, y_i)$ 插入最大堆，堆顶为当前最大的距离。
   • 若堆大小超过 $k$，弹出堆顶。
   • 最终堆中保留的即为最近的 $k$ 个充电桩。
4. 排序输出：将堆中元素取出，按 $(d_i, i)$ 升序排序后输出。

该方法时间复杂度为 $O(n \log k)$，空间复杂度 $O(k)$，适用于 $n,k$ 均可达 $10^6$ 的情形。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k; ll n;
    cin >> k >> n;  // 读取 k 和 n
    ll car_x, car_y;
    cin >> car_x >> car_y;  // 读取汽车坐标

    // 边界条件：k 为 0 或 大于 n 时输出 null
    if (k == 0 || k > n) {
        cout << "null";
        return 0;
    }

    // 优先队列：存储 (距离, 编号, x, y)，使用最大堆
    auto cmp = [](const tuple<ll,int,ll,ll>& a, const tuple<ll,int,ll,ll>& b) {
        if (get<0>(a) != get<0>(b))
            return get<0>(a) < get<0>(b);  // 距离大的排在堆顶
        return get<1>(a) < get<1>(b);      // 距离相等时编号大的排在堆顶
    };
    priority_queue<tuple<ll,int,ll,ll>, vector<tuple<ll,int,ll,ll>>, decltype(cmp)> pq(cmp);

    for (int i = 1; i <= n; ++i) {
        ll x, y;
        cin >> x >> y;  // 充电桩坐标
        ll d = llabs(car_x - x) + llabs(car_y - y);  // 计算行驶距离
        pq.emplace(d, i, x, y);
        if ((int)pq.size() > k) pq.pop();  // 保持堆大小为 k
    }

    // 取出堆中元素并排序
    vector<tuple<ll,int,ll,ll>> res;
    while (!pq.empty()) {
        res.push_back(pq.top());
        pq.pop();
    }
    sort(res.begin(), res.end(), [](auto &a, auto &b) {
        if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
        return get<1>(a) < get<1>(b);
    });

    // 输出结果：编号 x y distance
    for (auto &t : res) {
        cout << get<1>(t) << ' ' << get<2>(t) << ' ' << get<3>(t)
             << ' ' << get<0>(t) << '\n';
    }
    return 0;
}

Python

import sys
import heapq

def main():
    data = sys.stdin.read().split()
    k, n = map(int, data[:2])  # 读取 k, n
    car_x, car_y = map(int, data[2:4])  # 读取汽车坐标
    coords = data[4:]

    # 边界条件
    if k == 0 or k > n:
        print('null')
        return

    # 最大堆实现，存放 (-distance, -id, x, y)
    heap = []
    idx = 0
    for i in range(1, n+1):
        x = int(coords[idx]); y = int(coords[idx+1]); idx += 2
        d = abs(car_x - x) + abs(car_y - y)  # 计算行驶距离
        # 推入堆中，使用负值模拟最大堆
        heapq.heappush(heap, (-d, -i, x, y))
        if len(heap) > k:
            heapq.heappop(heap)

    # 提取并排序
    result = []
    while heap:
        d_neg, i_neg, x, y = heapq.heappop(heap)
        result.append((-d_neg, -i_neg, x, y))
    result.sort(key=lambda t: (t[0], t[1]))  # 按距离、编号排序

    # 输出
    for d, i, x, y in result:
        print(i, x, y, d)

if __name__ == '__main__':
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        int k = Integer.parseInt(first[0]);
        int n = Integer.parseInt(first[1]);

        String[] carPos = br.readLine().split(" ");
        long carX = Long.parseLong(carPos[0]);
        long carY = Long.parseLong(carPos[1]);

        // 边界条件
        if (k == 0 || k > n) {
            System.out.println("null");
            return;
        }

        // 最大堆，按距离和编号
        PriorityQueue<long[]> pq = new PriorityQueue<>(new Comparator<long[]>() {
            public int compare(long[] a, long[] b) {
                if (a[0] != b[0]) return Long.compare(b[0], a[0]);  // 距离大的在前
                return Long.compare(b[1], a[1]);  // 编号大的在前
            }
        });

        for (int i = 1; i <= n; i++) {
            String[] line = br.readLine().split(" ");
            long x = Long.parseLong(line[0]);
            long y = Long.parseLong(line[1]);
            long d = Math.abs(carX - x) + Math.abs(carY - y);  // 计算行驶距离
            pq.offer(new long[]{d, i, x, y});
            if (pq.size() > k) pq.poll();
        }

        // 收集并排序输出
        List<long[]> list = new ArrayList<>();
        while (!pq.isEmpty()) {
            list.add(pq.poll());
        }
        Collections.sort(list, new Comparator<long[]>() {
            public int compare(long[] a, long[] b) {
                if (a[0] != b[0]) return Long.compare(a[0], b[0]);
                return Long.compare(a[1], b[1]);
            }
        });

        for (long[] t : list) {
            System.out.println(t[1] + " " + t[2] + " " + t[3] + " " + t[0]);
        }
    }
}

题目内容

一个超大智能汽车测试场有多个充电桩，每个充电桩的位置由其在二维平面上的坐标 $(x,y)$ 表示。给定一辆智能汽车的当前位置 $(car_x,car_y)$ ，请设计一个高效的算法，找出给定智能汽车行驶到充电桩行驶距离最近的 $k$ 个充电桩井输出相关充电桩信息(编号、坐标、行驶距离)，且按行驶距离升序排序(最近行驶距离的排在最前面)，如果存在行驶距离相等的充电桩则按照充电桩的编号从小到大输出。汽车到充电桩的行驶距离的计算方法为 $abs(car_{x-x})+abs(car_{y-y})$ 注意：$abs$ 表示绝对值。

输入描述

1，第一行是 $2$ 个整数 $k$ $n$，空格间隔，第 $1$ 个整数 $k$ 表示需要输出到的行驶距离最近的充电桩的数量 $(0<=k<=1000000)$ ，第 $2$ 个整数 $n$ 表示充电桩的总数量 $(0<n<=1000000)$ 。

2，第 $2$ 行是长度为 $2$ 的整数数组 $car_x$ $car_y$，中间是空格间隔，表示智能汽车的当前位置坐标。

3，第 $3$ 行到第 $n+2$ 行是编号为 $1$ 到 $n$ 的充电桩的位置坐标

注意：坐标数值大小区间为：$[-2^{32},2^{31-1}]$

输出描述

一个二维数组，每一行是一个长度为 $4$ 的数组：编号 $x$ $y$ $distance$ ，编号表示充电桩的编号(介于 $1$ 到 $n$ 之间)、$x$ $y$ 表示充电的坐标, $distance$ 表示智能汽车到充电桩的行驶距离，从第 $1$ 行开始往下是按距离从小到大排序的。如果存在行驶距离相等的充电桩则按照充电桩的编号从小到大输出。如果 $k$ 为 $0$ 或者 $k$ 大于 $n$ ，输出字符串 $null$ 。

样例1

输入

3 5
0 0
1 4
5 6
2 3
7 8
3 -1

输出

5 3 -1 4
1 1 4 5
3 2 3 5

说明

到汽车行驶距离最近的三个充电桩的编号分别为 $5、1、3$ ，充电桩的坐标分别是 $3$ $-1$、$1$ $4$、$2$ $3$ ，到智能汽车坐标 $[0,0]$ 的行驶距离分别为 $4、5、5$。距离都为 $5$ 的充电桩 $1$ 的编号小于编号 $3$ 的充电桩，输出结果中编号小的在前。

样例2

输入

0 5
0 0
1 5
5 6
2 3
7 8
3 -1

输出

null

说明

$k$ 的值是 $0$ ，输出 $null$ 字符串