4445: 【入门】任务的最少完成时间(2119)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：41
解决：15
题目描述
小 同学接到了 个需要完成的任务，这 个任务必须按照接到的顺序完成，每个任务的完成时间为 。
由于任务非常艰巨，小 同学从老师那里领到了一张减负卡，用这张卡，小 可以从 个任务中任意的删除 个连续的任务，只需要完成剩余的任务。
请问，小 完成所有任务的总时间最少是多少？
输入
第 行，有两个整数 和 （，）。
接下来有 个整数，每个整数 表示每个任务的完成时间。（）
输出
一个整数，表示小 任务完成的最少时间。
样例输入 复制
5 2
1 3 2 5 4样例输出 复制
6提示
#include<bits/stdc++.h>
using namespace std;
/*
有n个数，可以删除连续的k个数
求剩余数的和最小是多少?
相当于求:连续k个数的和最大是多少?
*/
int n,k;const int N=1000010;
//为long long类型起别名
typedef long long LL;
LL a[N],b[N],ma; //b代表前缀和
int main(){
scanf("%d%d",&n,&k); //读入n个整数
for(int i=1;i<= n;i++){
scanf("%d",&a[i]);
//求前缀和
b[i]= b[i-1]+ a[i];
}
//求从每个数开始连续k个数的和，在所有的和中求最大
for(int i=1;i<=n-k+ 1;i++){
//区间范围:i~i+k-1
ma = max(ma,b[i+k-1]-b[i-1]);
}
//求剩余任务时间和的最小值
cout<<b[n]- ma;
return 0;
}