题解：P14242 [CCPC 2024 Shandong I] 分割序列

Confused_Fhy · 2025-10-20 22:41:55 · 题解

这题做了将近半个小时，发篇题解记录一下。

思路

第一遍写时发现思路完全错误，重构后开始按 k 的范围推，从一推到三后，不难发现题目就是要让你算出整个数组的后缀和并排序，然后从大到小加一遍输出即可。
当然，还有一些细节需要注意：后缀和数组的初始化用 memset 会直接炸掉，应直接把 n + 1 的位置初始化。

Code

这道题的代码还是比较简单的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rap(i, a, b) for(int i = a; i < b; i ++)
#define dwn(i, a, b) for(int i = a; i >= b; i --)
#define iosfst ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
int a[501000];
int pre[501000];
void solve(){
    int n; cin >> n;
    rep(i, 1, n) cin >> a[i];
    pre[n + 1] = 0;
    dwn(i, n, 1){
        pre[i] = pre[i + 1] + a[i];
    }
    int ans = pre[1];
    sort(pre + 2, pre + n + 1);
    cout << ans << ' ';
    dwn(i, n, 2){
        ans += pre[i];
        cout << ans << ' ';
    }
}
signed main() {
    iosfst;
    int t; cin >> t;
    while(t --){
        solve();
        cout << '\n';
    }
    return 0;
}

后缀和和前缀和还是比较重要的，值得我们去多刷题练习。