1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 全局变量定义:n为任务总数,m为可删除的连续任务数量(对应题目中的k) int n,m; // [2] arr数组:存储每个任务的完成时间(注意:此处类型为int,存在溢出风险) int arr[1000100]; // [3] srr数组:存储前缀和(long long类型,避免总和溢出) long long srr[1000100]={}; int main() { // [4] 输入任务总数n和可删除的连续任务数m cin>>n>>m; // [5] 循环读取n个任务的完成时间,存入arr数组(1基索引) for(int i=1;i<=n;i++){ cin>>arr[i]; } // [6] 初始化前缀和数组的第1项:前1个任务的时间和 srr[1]=arr[1]; // [7] 构建完整前缀和数组:srr[i] 表示前i个任务的总时间 for(int i=2;i<=n;i++){ srr[i]=srr[i-1]+arr[i]; } // [8] 初始化最大可删除子数组和为0 long long max_num=0; // [9] 滑动窗口遍历所有长度为m的连续子数组,找到其中的最大和 // 窗口左端点为i,右端点为i+m-1,确保窗口不越界 for(int i=1;i+m-1<=n;i++){ // [10] 计算当前窗口的和:前i+m-1项和 - 前i-1项和 long long num=srr[i+m-1]-srr[i-1]; // [11] 更新最大子数组和 max_num=max(max_num,num); } // [12] 最小总时间 = 所有任务总时间 - 最大可删除子数组和 cout<<srr[n]-max_num; return 0; }
- 1
信息
- ID
- 1370
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者