#qc006. 突击期的最大里程
突击期的最大里程
突击期的最大里程
题目描述
长征途中,为了在保存红军体力的同时加快战略转移,指挥部决定设立一个为期W天的"战略突击期"。由于翻雪山、过草地地形复杂,完全强求每天匀速行军是不现实的。指挥部制定了严格的评估标准:
在这连续的W天内(包含W-1次相邻的天数过渡),任何相邻两天的行军里程差的绝对值都不能超过D公里。如果有任意相邻两天的差值严格大于D,则会发生"剧烈颠簸”,该W天的突击期将被视为不合格。
请你编写程序,在给定的N天行军记录中,找出所有合格的"战略突击期”,并计算在这些合法的突击期中,这W天的行军总里程最大是多少。如果没有找到任何一个合格的突击期,则输出-1。
输入格式
第一行包含三个整数N,W,D
第二行包含N个非负整数,,....,表示这N天里每天的行军里程。
输出格式
输出一个整数,表示在所有合格的"战略突击期"中,这W天的行军总里程的最大值。如果没有合格的突击期,输出-1。
输入输出样例
5 3 5
1 3 5 7 9
21
数据规模与约定
【数据范围】
对于40%的数据,1≤W≤N≤2000。
对于100%的数据,1≤W≤N≤,0 ≤D≤
每天的行军里程0≤ ≤ 。
核心思路:
1.sy[i]标记位置i与 i+1的差值是否超标,记录是否有颠簸
2.s的窗口 [L,R]合法 ←内部所有相邻差都合法 ← sy[L..R-1]全为0
3.枚举滑动窗口的右端点,求出窗口左端点