道路最佳通信基站

题目描述

给定长度为 N 的数组 crossroads[]，其中 crossroads[i] 表示第 i 号路口基站的当前接入人数；以及覆盖范围 k。
基站 i 可覆盖路口 [max(0, i−k) … min(N−1, i+k)]。
小明从 0 号路口出发，走过第 i 段路（路口 i 到 i+1 之间）时，可连接所有覆盖该路段的基站，需选择接入人数最少的基站。
返回长度为 N−1 的数组 ret，其中 ret[i] 为第 i 段路的最佳基站编号。

解题思路

滑动窗口+单调队列

1. 转化窗口：第 i 段路所能连接的基站编号范围为

   L = max(0, i+1−k)   // 最早能覆盖该位置的基站
   R = min(N−1, i+k)   // 最后能覆盖该位置的基站
   

2. 维护最小值：我们需要在窗口 [L…R] 上快速查询最小值及其下标。

   • 使用双端队列（monotonic queue）维护当前窗口内的下标，保证队首是窗口内值最小的下标。
   • 当右端 R 增加时，将新下标入队，并在队尾弹出所有对应值 ≥ 新值的元素；
   • 当左端 L 增加时，如队首下标 < L，则将其出队。

3. 遍历 i 从 0 到 N−2：

   • 计算当前段的 L、R
   • 扩展右端到 R；收缩左端到 L
   • 队首即为最小值基站编号，存入 ret[i]。

边界与非法输入

• 若 crossroads 为空或 k < 1 或 k > N，返回 -1。

复杂度分析

• 时间复杂度：O(N)，每个下标最多进出队各一次。
• 空间复杂度：O(N)，用于存放双端队列和结果数组。

代码实现

以下是在原有实现基础上，加入标准输入读取与输出的完整代码。均含中文注释，逻辑清晰简洁。

Python 实现

from collections import deque
import sys

def best_station(cross, k):
    n = len(cross)
    # 非法输入检查
    if n < 2 or k < 1 or k > n:
        return -1
    dq = deque()     # 存放下标，保证 cross[dq] 单调递增
    res = []
    R = -1
    for i in range(n-1):
        # 计算第 i 段路可连接的基站编号范围
        L = max(0, i+1-k)
        newR = min(n-1, i+k)
        # 扩展右端到 newR
        while R < newR:
            R += 1
            # 弹出所有值 ≥ cross[R] 的下标
            while dq and cross[dq[-1]] >= cross[R]:
                dq.pop()
            dq.append(R)
        # 收缩左端，将队首下标 < L 的剔除
        while dq and dq[0] < L:
            dq.popleft()
        # 队首即为当前最小接入人数的基站下标
        res.append(dq[0])
    return res

if __name__ == "__main__":
    data = sys.stdin.readline().strip().split()
    if not data:
        print(-1)
        sys.exit(0)
    try:
        cross = list(map(int, data))
        k = int(sys.stdin.readline().strip())
    except:
        print(-1)
        sys.exit(0)
    ans = best_station(cross, k)
    if ans == -1:
        print(-1)
    else:
        print(" ".join(map(str, ans)))

Java 实现

import java.util.*;

public class Main {
    // 计算每段路的最佳基站
    public static List<Integer> bestStation(int[] cross, int k) {
        int n = cross.length;
        if (n < 2 || k < 1 || k > n) return Collections.singletonList(-1);
        Deque<Integer> dq = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        int R = -1;
        for (int i = 0; i < n - 1; i++) {
            int L = Math.max(0, i + 1 - k);
            int newR = Math.min(n - 1, i + k);
            // 扩展右端
            while (R < newR) {
                R++;
                while (!dq.isEmpty() && cross[dq.peekLast()] >= cross[R]) {
                    dq.pollLast();
                }
                dq.offerLast(R);
            }
            // 收缩左端
            while (!dq.isEmpty() && dq.peekFirst() < L) {
                dq.pollFirst();
            }
            res.add(dq.peekFirst());
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextLine()) {
            System.out.println(-1);
            return;
        }
        String[] parts = sc.nextLine().trim().split("\\s+");
        int n = parts.length;
        int[] cross = new int[n];
        try {
            for (int i = 0; i < n; i++) cross[i] = Integer.parseInt(parts[i]);
            if (!sc.hasNextInt()) throw new NumberFormatException();
            int k = sc.nextInt();
            List<Integer> ans = bestStation(cross, k);
            if (ans.size() == 1 && ans.get(0) == -1) {
                System.out.println(-1);
            } else {
                for (int i = 0; i < ans.size(); i++) {
                    System.out.print(ans.get(i));
                    if (i < ans.size() - 1) System.out.print(" ");
                }
                System.out.println();
            }
        } catch (Exception e) {
            System.out.println(-1);
        }
    }
}

C++ 实现

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

// 求每段路的最佳基站
vector<int> bestStation(const vector<int>& cross, int k) {
    int n = cross.size();
    if (n < 2 || k < 1 || k > n) return {-1};
    deque<int> dq;        // 存放下标，保证 cross[dq] 单调递增
    vector<int> res;
    int R = -1;
    for (int i = 0; i < n - 1; i++) {
        int L = max(0, i + 1 - k);
        int newR = min(n - 1, i + k);
        // 扩展右端
        while (R < newR) {
            R++;
            while (!dq.empty() && cross[dq.back()] >= cross[R]) {
                dq.pop_back();
            }
            dq.push_back(R);
        }
        // 收缩左端
        while (!dq.empty() && dq.front() < L) {
            dq.pop_front();
        }
        res.push_back(dq.front());
    }
    return res;
}

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

    string line;
    if (!getline(cin, line)) {
        cout << -1;
        return 0;
    }
    istringstream iss(line);
    vector<int> cross;
    int x;
    while (iss >> x) cross.push_back(x);

    int k;
    if (!(cin >> k)) {
        cout << -1;
        return 0;
    }

    vector<int> ans = bestStation(cross, k);
    if (ans.size() == 1 && ans[0] == -1) {
        cout << -1;
    } else {
        for (int i = 0; i < (int)ans.size(); i++) {
            if (i) cout << ' ';
            cout << ans[i];
        }
    }
    return 0;
}

题目内容

闹市区中有一条马路，马路从$0$号路口开始，到$N-1$号路口结束，在每个路口都架设了最新技术的通信基站，每个基站的信号可以覆盖前后各$k$个路口的范围，即第1个路口上的基站，可以覆盖$[i-k,i+k]$这两个路口之间的马路，因此用户的手机处于多个基站的覆盖范围中。每个基站会统计当前接入人数，为保障最佳通信质量，用户手机应选择连接人数最少的基站进行通讯。

这条马路一共$N$个路口，小明从$0$号路口出发向前走，求小明在每个路段中的最佳通讯基站。不考虑处于路口中间的特殊场景,只考虑在每个路段中的场景，例如第1个路段应为$0$号路口到$1$号路口之间的路段，如果基站覆盖范围$k=2$，此时最佳基站应为$0、1、2$中连接人数最少的基站。

输入描述

输入为两行

第一行长度为$N$的整数数组$crossroads[]$，数组元素以空格分隔，其中$crossroads[i]$表示$i$号路口基站的当前接入人数。

$1<=crossroads.length$数组长度$<=10^5，0<=crossroads[i]<=10^2$

第二行为基站覆盖范围$k$，$1 <= k <= crossroads.length$

非法输入返回$-1$

输出描述

返回一个数组$ret，ret[i]$表示$i$路段上最佳基站的编号，数组元素之间以空格分隔。例如$0$号路口到$1$号路口的路段，为$0$号路段，其最佳基站用$ret[0]$表示。

样例1

输入

3 5 8 7 6 7 4
2

输出

0 0 1 4 6 6 

说明

小明在第$1$段路时，位于$0$号和$1$号基站中间，此时可以连接到$0、1、2$这$3$个基站，而这三个基站中连接数最小的是$0$号基站($3$个人)，因此输出数组第一个元素应为$0$号基站。小明位于第$2$段路时，位于$1$号和$2$号基站中间，此时可以连接到$0、1、2、3$这$4$个基站，选择其中连接人数最小的基站，即$0$号基站($3$人)，因此输出数组第二个元素为$0$号基站。以此类推。

样例2

输入

9 8 7 6 7 8 9
2

输出

2 3 3 3 3 4

说明

小明在第$1$段路时，可以连接到的基站为$0、1、2$这$3$个基站，其中连接人数最小的基站为$2$号基站($7$人连接)，因此输出数组第一个元素为$2$号基站。以此类推。