这道题的正解是 单调队列 维护滑动窗口最值,但是我们用朴素解法 双指针+每次重算窗口min/max 也能在考试时拿到一定的分数。
题意:找最长连续区间 [L,R],使区间内任意两数差的绝对值都不超过 d。这等价于「区间最大值 − 区间最小值 ≤d」。多解时取起始编号最小的;若最长长度只有 1,输出 1 1。
朴素做法:右端点 r 从左到右扩大窗口;每次用线性扫描得到当前 [l,r] 的最大值与最小值,若 max−min>d,就不断右移左端点 l 并重新扫描最值,直到窗口合法。再按长度更新答案(只在更长时更新,保证起点最小)。
每次重算最值使整体约 O(n2)。小数据可以过;n 到 2×105 时会超时,需要后面的单调队列做法。
有n台医疗设备,编号为1到n,每台设备有一个当前的运行状态值。为了监控设备运行是否稳定,医院需要找出连续的设备序列,使得这些设备的运行状态值的差值都不超过某个阈值。
现在给定n台设备的运行状态值和一个阈值d,求最长的连续设备序列,使得序列中任意两台设备的运行状态值之差的绝对值不超过d。如果有多解,输出起始编号最小的序列。
第一行:两个整数n,d (1 ≤ n ≤ 200000, 0 ≤ d ≤ 10000),分别表示设备数量和允许的最大状态差值。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册