A17021. 突击期的最大里程
填空题
中等
知识点
题目描述
突击期的最大里程
题目描述
长征途中，为了在保存红军体力的同时加快战略转移，指挥部决定设立一个为期 W 天的“战略突击期”。
由于翻雪山、过草地地形复杂，完全要求每天匀速行军是不现实的。指挥部制定了严格的评估标准：在这连续的 W 天内，任何相邻两天的行军里程差的绝对值都不能超过 D 公里。如果存在相邻两天的差值严格大于 D，则会发生“剧烈颠簸”，该 W 天的突击期将被视为不合格。
请在给定的 N 天行军记录中，找出所有合格的“战略突击期”，并计算在这些合格的突击期中，这 W 天的行军总里程最大是多少。如果没有找到任何一个合格的突击期，则输出 -1。
输入描述
第一行包含三个正整数 N, W, D，分别表示总记录天数、突击期的天数要求、以及相邻两天的最大允许里程差。
第二行包含 N 个非负整数 a1, a2, ..., aN，表示这 N 天里每天的行军里程。
输出描述
输出一个整数，表示在所有合格的“战略突击期”中，这 W 天的行军总里程的最大值。如果没有合格的突击期，输出 -1。
样例输入
7 3 2
10 11 10 15 16 14 20样例输出
45参考答案
#include <bits/stdc++.h>
using namespace std;
long long a[1000005];
int main() {
int n, w;
long long d;
cin >> n >> w >> d;
for (int i = 1; i <= n; i++) cin >> a[i];
if (w == 1) {
long long ans = a[1];
for (int i = 2; i <= n; i++) ans = max(ans, a[i]);
cout << ans;
return 0;
}
long long sum = 0, ans = -1;
int bad = 0;
for (int i = 1; i <= w; i++) sum += a[i];
for (int i = 2; i <= w; i++)
if (abs(a[i] - a[i - 1]) > d) bad++;
if (bad == 0) ans = sum;
for (int l = 2; l + w - 1 <= n; l++) {
int r = l + w - 1;
sum = sum - a[l - 1] + a[r];
if (abs(a[l] - a[l - 1]) > d) bad--;
if (abs(a[r] - a[r - 1]) > d) bad++;
if (bad == 0) ans = max(ans, sum);
}
cout << ans;
return 0;
}答案解析
1. 每个连续 W 天就是一个窗口。
2. 用 sum 记录当前窗口的总里程。
3. 用 bad 记录当前窗口中有多少对相邻天数不合格。
4. 当窗口右移时，减去离开的天数，加上新进入的天数，同时更新相邻差是否合格。
5. 如果 bad == 0，说明当前窗口合格，用它的总和更新答案。
上一题
下一题