题目：【CSGRound2】光骓者的荣耀 - 洛谷

题目大意

 用最少时间要将所有城市全部访问完，若有传送器可使用传送器。

坑点

1.需要考虑传送器数量与城市的数量 ，若传送器大于城市输出0

2.需要考虑数据范围较大，long long int 

数据范围

 开一个大于10的6次方的数据

思路

1.先考虑特例

2.由于需要最短时间，所以在有传送器的情况下使用传送器到最后一个城市 

代码

#include<iostream>
#include<stdio.h>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<stack>
#include<set>
using namespace std;
const int N=1e6+10;//取一个固定数据 
long long int sum[N];//数组 
long long int n,k;//数据范围要求 
int main()
{cin>>n>>k;if(k>=n-1)//传送器>=城市数量 ，特例情况 {cout<<"0"<<endl;//直接用传送器，所以输出0 return 0;}for(int i=1;i<=n-1;i++){long long int x;// 定义一个数表示传送的时间 cin>>x;sum[i]=sum[i-1]+x;//前缀和公式。表示第i个需要第i-1个的时间加上到第i个需要x时间 }long long int maxn=0;//定义一个数据和量 for(int i=k;i<=n-1;i++){maxn=max(sum[i]-sum[i-k],maxn);//表示用传送器花费的最多时间 }cout<<sum[n-1]-maxn<<endl;//得出一个用的最少时间 return 0;
}

总结

1.需要考虑特例和数据范围

2.需要使用前缀和公式来储存所用的时间