You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
24 lines
979 B
24 lines
979 B
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
#define int long long
|
|
#define endl "\n"
|
|
const int N = 1000010;
|
|
int n, k;
|
|
int a[N], s[N];
|
|
int ans = LONG_LONG_MAX; // 预求最小先设最大
|
|
|
|
signed main() {
|
|
cin >> n >> k;
|
|
for (int i = 2; i <= n; i++) { // i代表第i个城市
|
|
cin >> a[i]; // a[i]代表第i-1个城市到第i个城市需要的时间
|
|
s[i] = s[i - 1] + a[i]; // 利用前缀存储从第1个城市到第i+1个城市的累积时间
|
|
}
|
|
// 感悟：代码越多，可读性越强
|
|
for (int i = 1; i <= n; i++) { // 遍历每个城市
|
|
int far = i + k; // 传送到最远的点
|
|
if (far >= n) far = n; // 最远不能超过n点
|
|
int time = s[i] + s[n] - s[far]; // s[n]-s[far]= 剩余道路需要走的时间,s[i]:前面道路需要走的时间
|
|
ans = min(ans, time); // 取最小值
|
|
}
|
|
cout << ans << endl; // 输出
|
|
} |