题目链接
知识点:前缀和、模拟
题目大意:
有 n个城市,每两个城市之间有一条公路,和 k个传送带,可传送到第 i+k 和 i-k 个城市,传送带至多使用一次,问最少要花费的时间是多少?
解题思路:
1.判断是否有传送带
2.有传送带的话,那段花费的时间最长
AC代码:
#include#include #include #include using namespace std; const int N=1e6+10; long long int sum[N]; long long int a[N]; long long int n,k; long long int maxn=-1; int main() { cin>>n>>k;//n城市数,k传送带数 if(k>=n-1) { cout<<"0"< 总的数量,则不需花费时间可可直接传送过去 return 0; } for(int i=1;i<=n-1;i++) { cin>>a[i];//每段花费的时间 sum[i]=sum[i-1]+a[i];//求出所有时间之和 } for(int i=k;i<=n-1;i++) { maxn=max(sum[i]-sum[i-k],maxn);//求出最大的花费的时间 } cout< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)