题解

题目描述

在一条长度为 $N$ 的道路上，路口编号从 $0$ 到 $N-1$。每个路口 $i$ 都安装了一个基站，并统计了当前接入人数为 $crossroads[i]$。每个基站的信号覆盖范围为前后各 $k$ 个路口，即第 $i$ 号基站覆盖区间为 $[\,i-k,\;i+k\,]$（边界越界取到 $0$ 或 $N-1$）。行驶在第 $i$ 号路段（即在路口 $i$ 和 $i+1$ 之间）时，手机可连接所有覆盖该路段的基站，用户应选择接入人数最少的基站。

思路

要在每个路段上快速求出滑动区间内的最小值位置，可用双端队列（deque）维护“单调队列”，以支持区间左右端点同时移动的场景：

1. 定义区间端点

   • 第 $i$ 号路段的左端点：$$L_i = \max(0,\,i+1-k)$$
   • 右端点：$$R_i = \min(N-1,\,i+k)$$

2. 初始化

   • 对应第 $0$ 号路段，区间为 $[\,0,\; \min(N-1,k)\,]$，将所有下标依次入队，同时维护队内从队首到队尾对应的 $crossroads[\cdot]$ 值呈单调递增。

3. 滑动更新
   对每个后续路段 $i$（从 $1$ 到 $N-2$）：

   • 右端扩展：若 $R_i>R_{i-1}$，将新的下标 $R_i$ 按“单调”规则加入队尾。
   • 左端收缩：若队首元素的下标 $idx<L_i$，则将其弹出。
   • 队首即最小：此时队首存储的下标即为区间内最小值位置，令 $ret[i]=\text{队首下标}$。

整个过程对每个下标最多入队一次、出队一次，时间复杂度为 $O(N)$。

C++

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

vector<int> bestStation(const vector<int>& crossroads, int k) {
    int N = crossroads.size();
    if (N < 2 || k < 1 || k > N) return {}; // 非法输入

    vector<int> ret(N-1);
    deque<int> dq;

    // 初始化第0号路段的区间 [0, min(N-1, k)]
    int R0 = min(N-1, k);
    for (int i = 0; i <= R0; ++i) {
        // 单调队列：新元素比尾部大时直接入队，否则弹尾
        while (!dq.empty() && crossroads[i] <= crossroads[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    ret[0] = dq.front();

    // 依次处理后续路段
    for (int i = 1; i < N-1; ++i) {
        int Li = max(0, i+1-k);
        int Ri = min(N-1, i+k);

        // 扩展右端
        if (Ri > R0) {
            int idx = Ri;
            while (!dq.empty() && crossroads[idx] <= crossroads[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(idx);
            R0 = Ri;
        }
        // 收缩左端
        while (!dq.empty() && dq.front() < Li) {
            dq.pop_front();
        }
        ret[i] = dq.front();
    }
    return ret;
}

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

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

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

    auto ans = bestStation(crossroads, k);
    if (ans.empty()) {
        cout << -1;
    } else {
        for (int i = 0; i < (int)ans.size(); ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
    }
    return 0;
}

Python

from collections import deque
import sys

def best_station(crossroads, k):
    n = len(crossroads)
    if n < 2 or k < 1 or k > n:
        return None  # 非法输入
    ret = [0] * (n-1)
    dq = deque()

    # 初始化第0号路段
    R0 = min(n-1, k)
    for i in range(R0+1):
        while dq and crossroads[i] <= crossroads[dq[-1]]:
            dq.pop()
        dq.append(i)
    ret[0] = dq[0]

    # 滑动其余路段
    for i in range(1, n-1):
        Li = max(0, i+1-k)
        Ri = min(n-1, i+k)
        if Ri > R0:
            idx = Ri
            while dq and crossroads[idx] <= crossroads[dq[-1]]:
                dq.pop()
            dq.append(idx)
            R0 = Ri
        while dq and dq[0] < Li:
            dq.popleft()
        ret[i] = dq[0]
    return ret

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

Java

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

public class Main {
    // 使用双端队列维护滑动区间最小值下标
    public static List<Integer> bestStation(int[] crossroads, int k) {
        int n = crossroads.length;
        if (n < 2 || k < 1 || k > n) return null; // 非法输入

        List<Integer> ret = new ArrayList<>();
        Deque<Integer> dq = new LinkedList<>();

        // 初始化第0号路段区间 [0, min(n-1,k)]
        int R0 = Math.min(n-1, k);
        for (int i = 0; i <= R0; i++) {
            while (!dq.isEmpty() && crossroads[i] <= crossroads[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.offerLast(i);
        }
        ret.add(dq.peekFirst());

        // 处理后续路段
        for (int i = 1; i < n-1; i++) {
            int Li = Math.max(0, i+1-k);
            int Ri = Math.min(n-1, i+k);
            if (Ri > R0) {
                int idx = Ri;
                while (!dq.isEmpty() && crossroads[idx] <= crossroads[dq.peekLast()]) {
                    dq.pollLast();
                }
                dq.offerLast(idx);
                R0 = Ri;
            }
            while (!dq.isEmpty() && dq.peekFirst() < Li) {
                dq.pollFirst();
            }
            ret.add(dq.peekFirst());
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().trim().split("\\s+");
        int[] crossroads = Arrays.stream(parts).mapToInt(Integer::parseInt).toArray();
        int k;
        try {
            k = Integer.parseInt(br.readLine().trim());
        } catch (Exception e) {
            System.out.println(-1);
            return;
        }
        List<Integer> ans = bestStation(crossroads, k);
        if (ans == null) {
            System.out.println(-1);
        } else {
            for (int i = 0; i < ans.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(ans.get(i));
            }
        }
    }
}

题目内容

闹市区中有一条马路，马路从$0$号路口开始，到$N-1$号路口结束，在每个路口都架设了最新技术的通信基站，每个基站的信号可以覆盖前后各$k$个路口的范围，即第$i$个路口上的基站，可以覆盖$[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$号基站。以此类推。