题解

题目描述

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

思路

题目内容

闹市区中有一条马路，马路从$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$号基站。以此类推。