牛客算法周周练1

链接：https://ac.nowcoder.com/acm/contest/5086/A
来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

Today HH finds a non-decreasing sequence(a₁,a₂....a_n,a_i≤a_i+1), he thinks it's not beautiful so he wants to make it beautiful.

To make it, HH will choose exactly one number and move it forward at least k steps(i.e. you can move a_i to a_j if k≤i−j), and then he defines the beautiful value F(n) as

HH asks you to calculate max(F(n))

输入描述:

The first line contains an positive integer T(1≤T≤10), represents there are T test cases.

For each test case:

The first line contains two positive integers n,k(1≤n≤10⁵,1≤k<n)，the length of the sequence ,the least steps you need to move.

The second line contains n integers a₁,a₂…a_n(1≤a_i≤10⁸) - the sequence.

输出描述:

For each test case, you should output the max F(n).

输入

输出

46
50
53

说明

In the first example, you can move the fifth number 4 for 3 steps and make the sequence become [4,1,1,3,5], then the beautiful value is 4×1+1×2+1×3+3×4+5×5=46.
You can also move the fifth number to make it become [1,5,1,3,4], the beautiful value is also 46.
In the second example, you can move the fifth number 5 for 2 steps and make the sequence become [1,1,5,3,4]
In the third example, you can move the second number 1 for 1 steps and then the sequence is still [1,1,3,4,5]

备注:

scanf is commended。

因为给出的序列是单调不降的，所以给出的顺序F(n)一定是最大的。

所以只需要移动最小的距离使影响最小，即移动 k 个单位。

考虑移动每个数对总和产生的影响，找到最大值即可。

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 #define pb push_back
 4 const int INF = 0x3f3f3f3f;
 5 const double eps = 1e-8;
 6 const int mod = 1e9+7;
 7 const int maxn = 1e5+10;
 8 using namespace std;
 9 
10 LL a[maxn];
11 LL sum[maxn];
12 
13 int main()
14 {
15     #ifdef DEBUG
16     freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
17     #endif
18     
19     int T;
20     scanf("%d",&T);
21     while(T--)
22     {
23         int n,m;
24         scanf("%d %d",&n,&m);
25         LL all = 0;
26         for(int i=1;i<=n;i++)
27         {
28             scanf("%d",&a[i]);
29             sum[i] = sum[i-1]+a[i];
30             all+=i*a[i];
31         }
32         LL ans = 0;
33         for(int i=1+m;i<=n;i++)
34         {
35             LL t = all+(sum[i-1]-sum[i-1-m])-a[i]*m;
36             ans=max(ans,t);
37         }
38         printf("%lld
",ans);
39     }
40 
41     return 0;
42 }