2025-10-17 学习日记

今日学习记录

1. Problem - F - Codeforces

关键词：贪心 前缀和 排序 问题分析： 把数组分成 k 段,si 为第 i 段的总和,求$s1+2*s2+3*s3 ...+n*sn = ans$ 给出多组测试数据,每组都要进行 k 次切割,每次输出经过 k 次切割得到的最大 ans 值

核心思路: (我看到这道题的时候想到的是哈夫曼编码贪心,是求带权路径最短的,这道题是求最大) 先一个小贪心,我要把数组分成 k 段,然后求最大权值,后面的段乘的值越大结果越优,所以我们要先求后缀和,再对后缀和数组进行排列,把大的放在前面,要求 k 段和,其实不用枚举每个段再总和,直接利用后缀和来进行片段的累加 例如: [1,2,3,4,5]这段后缀和为[15,14,12,9,5],我们可以看当我们使用 15+12 时,其实就是 04 和 24 的片段叠加和,等价于 02 的数总和加上 2 倍的 24 的总和,这样就达到题目要求的了,排序就是要求最大的这个后缀,往前加小的时候倍数就小 **最终代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll a[N]; 
int n;
int main(){
	int q=1;
	cin >> q;
	while(q--){
        cin>>n;
	    for(int i=1;i<=n;i++) cin>>a[i];
	    for(int i=n-1;i>=1;i--) a[i]+=a[i+1];
	    sort(a+2,a+n+1);
	    ll sum=a[1];
	    cout<<sum<<" ";
	    for(int i=n;i>=2;i--) {
	        sum+=a[i];
	        cout<<sum<<" ";
	    }
	    cout<<endl;
    }
    return 0;
}

学到的点：

1. 贪心

2. 题目名称题目来源标号

关键词： 问题分析：

核心思路

最终代码：

学到的点： 1.