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

· · 题解

P党来发一发/kk(C++也会一点，代码贴的时候两种都放了，但是由于C++刚学，所以码风较丑，大佬们凑合一下呗）

洛谷月赛的第一题，果然是增加信心题，连我这样的蒟蒻都过了。

题目传送门

题意已经说的非常清楚了。这里不再赘述。

本人忘记传送东西的名字了，就叫传送门好了QAQ

由于是从第一个地方走到第n个地方，而且，a[i]>=0所以传送门只有从i走到i+k才会减少代价,那么我们就可以用一个前缀和优化一下，在第i个位置使用时，传送门会把这个人传送到i+k的位置，减少的代价就为a[i+k]-a[i]（我们设a为前缀和数组），这样找个最大的a[i+k]-a[i]，此时i就是传送门使用的位置了，距离和即为：从1到i的距离，加上从i+k+1到n的距离，用前缀和数组a表示，即为：a[i]+a[n]-a[i+k]

坑点：可以在第0个位置使用传送门

看一个例子吧

5 2
10 10 1 1

显然，这个例子答案为2，但是如果并没有考虑在第0个位置使用传送门的话，答案会变成11，测试数据里就有这种情况，如果没有考虑这个的话，只会得到92分。

另一个坑点是开int64（long long），不然40分

注：代码中m=0的时候特判了一下，实际上没有这个必要。

Pascal代码：
var n,i:longint;
m,max,k:int64;
a:array[0..1000000] of int64;

begin
readln(n,m);
n:=n-1;
for i:=1 to n do
  begin
  read(a[i]);a[i]:=a[i-1]+a[i];
  end;
if m=0 then writeln(a[n])
else
  begin
  for i:=0 to n-m do
    if a[i+m]-a[i]>max then
      begin
      max:=a[i+m]-a[i];k:=i;
      end;
  writeln(a[k]+a[n]-a[k+m]);
  end;
end.
C++代码：
#include<cstdio>
long long n,m,k,max,a[1000009];
using namespace std;
int main()
{
    scanf("%lld%lld",&n,&m);
    n--;
    for (long long  i=1;i<=n;i++)
      {
        scanf("%lld",&a[i]);a[i]+=a[i-1];
      }
    if (m==0) 
      {
        printf("ll%d\n",a[n]);
             }    
    else
    {
        for (long long i=0;i<=n-m;i++)
          if (a[i+m]-a[i]>max)
          {
            max=a[i+m]-a[i];k=i;
          }
    printf("%lld\n",a[k]+a[n]-a[k+m]);    
             }  
  return 0;              
 }