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

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

思路

第一遍写时发现思路完全错误，重构后开始按

k

的范围推，从一推到三后，不难发现题目就是要让你算出整个数组的后缀和并排序，然后从大到小加一遍输出即可。
当然，还有一些细节需要注意：后缀和数组的初始化用 memset 会直接炸掉，应直接把

n + 1

的位置初始化。

Code

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

CPP

#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;
}

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

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

文章操作

思路

Code

相关推荐

评论

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