#qc006. 突击期的最大里程

突击期的最大里程

突击期的最大里程

题目描述

​ 长征途中,为了在保存红军体力的同时加快战略转移,指挥部决定设立一个为期W天的"战略突击期"。由于翻雪山、过草地地形复杂,完全强求每天匀速行军是不现实的。指挥部制定了严格的评估标准:

​ 在这连续的W天内(包含W-1次相邻的天数过渡),任何相邻两天的行军里程差的绝对值都不能超过D公里。如果有任意相邻两天的差值严格大于D,则会发生"剧烈颠簸”,该W天的突击期将被视为不合格。

​ 请你编写程序,在给定的N天行军记录中,找出所有合格的"战略突击期”,并计算在这些合法的突击期中,这W天的行军总里程最大是多少。如果没有找到任何一个合格的突击期,则输出-1。

输入格式

​ 第一行包含三个整数N,W,D

​ 第二行包含N个非负整数a1a_1,a2a_2,....aNa_N,表示这N天里每天的行军里程。

输出格式

​ 输出一个整数,表示在所有合格的"战略突击期"中,这W天的行军总里程的最大值。如果没有合格的突击期,输出-1。

输入输出样例

5 3 5
1 3 5 7 9
21

数据规模与约定

【数据范围】

​ 对于40%的数据,1≤W≤N≤2000。

​ 对于100%的数据,1≤W≤N≤10510^5,0 ≤D≤ 10910^9

​ 每天的行军里程0≤ aia_i ≤ 10910^9。

核心思路:

1.sy[i]标记位置i与 i+1的差值是否超标,记录是否有颠簸

2.s的窗口 [L,R]合法 ←内部所有相邻差都合法 ← sy[L..R-1]全为0

3.枚举滑动窗口的右端点,求出窗口左端点