C - Index × A(Continuous ver.)

题目大意：

给定n个数(\(a_1,a_2...a_n\))，从中选连续m个数，这m个数的和为：\(\sum_{i=1}^mi*b_i\)
求最大的和为多少。

\(1<=m<=n<=2*10^5\)
\(-2*10^5<=a_i<=2*10^5\)

解题思路

首先 m 个数为一组，那么最多有 n - m + 1 组，这个数量是可以被遍历的，但是每一组的值需要在 O(1) 的时间内算出来。

举例：

7 3
1 2 3 4 5 6 7

其中前一组为 \(2*1\ \ 3*2\ \ 4*3\)的和，后一组为\(3*1\ \ 4*2\ \ 5*3\)的和

前一组-后一组：\(2*1\ \ 3*1\ \ 4*1\ \ -5*3\)，

可以看出，结果可以表示为：(上一组的所有数的一倍之和) - (当前组最后一个数的 m 倍)，连续的几个数之和显然可以用前缀和解决，单独的一个数的倍数，不用解决，直接算。

上面的的结果是：前一组 - 后一组( a - b = sum - m*x)，那么对于后一组 b = a + mx - sum，

实现过程：预先算出第一组，从第二组开始，每一组采用上面的式子，算出当前组的值，并维护最大值。

在计算过程中，注意使用前缀和的下标即可

for (int i = 2; i <= n - m + 1; ++i) {
        ans[i] = ans[i - 1] + m * a[m + i - 1] - (s[m + i - 2] - s[i - 2]);
//当前组的最后一个值为，当前组的第一个数，也就是i，+m-1即可，i+m-1
//上一组的最后一个数，为当前组倒数第二个数，即i+m-1再-1 -> i+m-2
//上一组的第一个数为当前组的第一个数的前一个，即i-1,但是前缀和需要减再前面一个的前缀,即i-2
        maxx = max(maxx, ans[i]);
        //cout << "ans: " << ans[i] << endl;
    }

AC

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 1e5 + 5;

//kmp kruskal lca 线段树 线性筛 组合数 线性同余方程 逆元
int n, m;

void solve () {
    cin >> n >> m;
    vector<ll>a(n + 1);
    vector<ll>s(n + 1);
    vector<ll>ans(n + 1);
    a[0] = s[0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    for (int i = 1; i <= m; ++i) {
        ans[1] += i * a[i];
    }
    ll maxx = ans[1];
    //cout << "ans: " << ans[1] << endl;
    for (int i = 2; i <= n - m + 1; ++i) {
        ans[i] = ans[i - 1] + m * a[m + i - 1] - (s[m + i - 2] - s[i - 2]);
        maxx = max(maxx, ans[i]);
        //cout << "ans: " << ans[i] << endl;
    }
    cout << maxx << endl;
}

signed main() {
    IOS
    int T;
    T = 1;
    //cin >> T;
    while (T--)solve();
    return 0;
}