题解 P5638 【【CSGRound2】光骓者的荣耀】

沉冥Charming · 2019-11-10 08:07:45 · 题解

• 这是一道难度入门的良心题~

• 题意很明了，可以传送一次，求1到n耗费的最少时间

• 很明显，可以贪心，最长的k段选择传送，其余步行

• 求两地之间用时使用前缀和，sum[ i ]表示a1到ai之和

• 那么使用传送器可以节省时间可表示为sum[ k + i ] - sum[ i ]

• 扫一遍找到节省时间最大值，答案即是1到n之间步行用时减去传送节省时间

• 然而稍不注意就只有92分，似乎坑到了一部分人（比如本蒟蒻）

• 原因很简单，sum[ k + i ] - sum[ i ]中的i要从0开始循环而不是从1开始

• 显而易见，若k=1，那么sum[1 +1 ] - sum[1]表示的是2 , 3 两地之间用时

• 所以如果从1开始循环就会漏掉从1地到1+k地之间的用时

• 从0开始循环就可以ac了！！！

• ac代码如下：

  
  #include <iostream>
  #include <cstdio>
  using namespace std;
  #define ull unsigned long long //防止不开long long见祖宗
  #define ll unsigned long long
  ull n,k,sum[1000005],cnt;
  ll qr()//快读，让您的排名更好看
  {
  ll ret=0;
  char c=getchar();
  while (c<'0'||c>'9')
      c=getchar();
  while (c>='0'&&c<='9')
  {
      ret=(ret<<1)+(ret<<3)+c-'0';
      c=getchar();
  }
  return ret;
  }
  int main()
  {
  //cin>>n>>k; //cin太慢了
  n=qr(),k=qr();
  for (int i=1; i<n; i++)
  {
      ull a;
      //cin>>a;
      a=qr();
      sum[i]=sum[i-1]+a; //前缀和
  }
  for (int i=0; i+k<n; i++) //从0开始循环
      cnt=max(cnt,sum[i+k]-sum[i]); //找节省时间最大值
  cout<<sum[n-1]-cnt;
  return 0;
  }