A125924 题解

题干分析

有一个长度为 $n$ 的数组，把这个数组切成连续的三段，它们的和分别记作 $s_1,s_2,s_3$。然后计算最大值和最小值的差，求这个差的最小值。

思路

可以用枚举做本题，时间复杂度为 $O(n^2)$，不会 $TLE$。
先提前算出数组的前缀和，记在 $pre$ 数组里，方便以后的求和。然后枚举，第一层循环到 $n-2$，第二层循环到 $n-1$，这时，$pre$ 数组就有用了。不难发现，$s_1 \gets pre_i,s_2 \gets pre_j - pre_i,s_3 \gets pre_n - pre_j$。然后算出最大值和最小值的差，再和当前最小的差比较即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[505];
unsigned long long pre[505],ans=ULLONG_MAX;//unsigned long long是无符号超长整型，ULLONG_MAX是无符号超长整型的最大值
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];//计算前缀和
    }
    for(int i=1;i<=n-2;i++){
        for(int j=i+1;j<=n-1;j++){
            unsigned long long s1=pre[i],s2=pre[j]-pre[i],s3=pre[n]-pre[j];//计算s₁,s₂,s₃的值
            unsigned long long ma=max(max(s1,s2),s3),mi=min(min(s1,s2),s3);
            ans=min(ans,ma-mi);//更新答案
        }
    }
    cout<<ans;
}

最后

如果有看不懂的，可以发在讨论区。制作不易，点个赞再走吧！