csp信奥赛C++高频考点专项训练：【滑动窗口】案例4：突击期的最大里程

csp信奥赛C高频考点专项训练【滑动窗口】案例4突击期的最大里程【题目描述】长征途中为了在保存红军体力的同时加快战略转移指挥部决定设立一个为期W天的“战略突击期”。由于翻雪山、过草地地形复杂完全强求每天匀速行军是不现实的。指挥部制定了严格的评估标准在这连续的W天内包含W-1次相邻的天数过渡任何相邻两天的行军里程差的绝对值都不能超过D公里。如果有任意相邻两天的差值严格大于D则会发生“剧烈颠簸”该W天的突击期将被视为不合格。请你编写程序在给定的N天行军记录中找出所有合格的“战略突击期”并计算在这些合法的突击期中这W天的行军总里程最大是多少。如果没有找到任何一个合格的突击期则输出-1。【输入格式】第一行包含三个正整数N、W、D分别表示总记录天数、突击期的天数要求以及相邻两天的最大允许里程差。第二行包含N个非负整数a1, a2, ..., aN表示这N天里每天的行军里程。【输出格式】输出一个整数表示在所有合格的“战略突击期”中这W天的行军总里程的最大值。如果没有合格的突击期输出-1。【数据范围】对于 40% 的数据1 ≤ W ≤ N ≤ 2000 1 ≤ W ≤ N ≤ 20001≤W≤N≤2000。对于 100% 的数据1 ≤ W ≤ N ≤ 10 5 0 ≤ D ≤ 10 9 1 ≤ W ≤ N ≤ 10^50 ≤ D ≤ 10^91≤W≤N≤1050≤D≤109。每天的行军里程0 ≤ a i ≤ 10 9 0 ≤ ai ≤ 10^90≤ai≤109。以下是两个符合题意的输入输出样例样例 1输入5 3 2 1 3 2 4 3输出9说明所有长度为 3 的连续子序列[1, 3, 2]相邻差为 2 和 1均 ≤ 2合法和为 6[3, 2, 4]相邻差为 1 和 2均 ≤ 2合法和为 9[2, 4, 3]相邻差为 2 和 1均 ≤ 2合法和为 9最大合法和为 9。样例 2输入4 2 0 5 3 5 3输出-1说明W 2要求相邻两天的里程差绝对值不超过D 0即两天里程必须相等。所有长度为 2 的窗口[5, 3]差为 2不合法[3, 5]差为 2不合法[5, 3]差为 2不合法没有合格突击期因此输出-1。思路分析需要找到所有长度为W的连续子序列使得子序列内部相邻两天的里程差绝对值均不超过D。先预处理相邻两天的合法性用布尔数组ok[i]表示第i天与第i1天是否合法1 ≤ i N。使用滑动窗口遍历所有可能的起始位置l从 1 到N-W1。维护当前窗口内不合法的相邻对数量bad以及当前窗口的里程和sum。初始窗口[1, W]时统计ok[1..W-1]中不合法个数同时计算sum a[1]...a[W]。若bad 0则当前窗口合法更新答案ans max(ans, sum)。窗口右移时移出左边界a[l]同时原先窗口内包含的相邻对ok[l]离开因为新窗口起始为l1不再包含ok[l]。移入右边界a[lW]新加入的相邻对是ok[lW-1]因为新窗口包含从l1到lW相邻对索引为l1到lW-1但实际上是新增了ok[lW-1]即第lW-1天与第lW天的合法性。更新bad若离开的ok[l]不合法则bad--若新增的ok[lW-1]不合法则bad并更新sum a[lW] - a[l]。当W 1时无需检查相邻差任意单日都合法直接输出所有天数中的最大值即可。时间复杂度 O(N)空间复杂度 O(N)。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;//简化长整型intN,W;ll D,a[100010];intmain(){cinNWD;for(inti1;iN;i){cina[i];}if(W1){//单日窗口无需检查相邻差ll ans0;for(inti1;iN;i){if(a[i]ans)ansa[i];//找最大里程}coutans;return0;}boolok[N];//ok[i]表示第i天与第i1天是否合法i范围1~N-1for(inti1;iN-1;i){ll diffa[i1]-a[i];if(diff0)diff-diff;//绝对值ok[i](diffD);}ll ans-1;//初始无合法窗口intbad0;//当前窗口内不合法相邻对个数ll sum0;//当前窗口里程和//初始化第一个窗口 [1, W]for(inti1;iW;i){suma[i];}for(inti1;iW-1;i){if(!ok[i])bad;}if(bad0)anssum;//第一个窗口合法//滑动窗口起始位置l从2到N-W1for(intl2;lN-W1;l){//移出左边界第l-1天的相邻对ok[l-1]离开窗口if(!ok[l-1])bad--;//移入右边界第lW-1天与第lW天的相邻对ok[lW-1]加入窗口if(!ok[lW-1])bad;//更新窗口和移出a[l-1]移入a[lW-1]因为新窗口为[l, lW-1]suma[lW-1]-a[l-1];if(bad0){//当前窗口合法if(sumans)anssum;}}coutans;return0;}完整信奥赛C普及组CSP-J一等奖通关刷题题单及题解请关注专栏https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}