题目网址：http://class.51nod.com/Challenge/Problem.html#problemId=1065
N个整数组成的序列a[1],a[2],a[3],…,a[n]，从中选出一个子段（a[i],a[i+1],…a[j]）
使这个子段的和>0，并且这个和是所有和>0的子段中最小的。
例如：4，-1，5，-2，-1，2，6，-2。-1，5，-2，-1，序列和为1，是最小的。
第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N+1行：N个整数
输出最小正子段和。
8 4 -1 5 -2 -1 2 6 -2
1
这道题我们可以利用 前缀和+结构体排序 来解决
首先，大家来看一下：我们假设我们先把所有数字的前缀和都求出来了
（拿样例来举例）
prefix_sum：{0,4,3,8,6,5,7,13,11}
接下来排个序，为什么要排序呢？
因为我们枚举每一个前缀和，对当前的前缀和，找到一个与它最接近的前缀和，这两者之差便有可能成为答案。
所有的前缀和求出来排序，排过序之后相邻的两项（两个前缀和）一定是值最接近的。
在找相邻两项的差的时候也要注意判断前缀和的前后关系。（必须是后面的大数-前面的小数）
每个区间的和都可以看做是前缀和的差。
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; long long n, ans=1e9; struct node{//a[i]里存的 long long sum;//到目前a[i]的前缀和 long long key;//a[i]的原始下标 }a[50010]; bool cmp(node x, node y){ return x.sum < y.sum;//按照前缀和升序排序 } int main(){ cin >> n; a[0].key = 0; a[0].sum = 0; for(int i = 1;i <= n;i++){ cin >> a[i].sum;//输入a[i] a[i].key = i;//a[i]的原始下标为i if(i != 1){//如果至少已经有1个数了 a[i].sum += a[i-1].sum;//它的前缀和为上一个数加上现在这个数 } } sort(a, a+n+1, cmp);//结构体排序 for(int i = 0;i <= n;i++){ //如果大范围的原始下标比小范围的原始下标要大，说明大范围里面是小范围，满足条件 //如果大范围的前缀减去小范围的前缀和大于0，满足条件 if(a[i].key < a[i+1].key && a[i+1].sum - a[i].sum > 0){//如果满足条件 ans = min(ans, a[i+1].sum - a[i].sum);//判断最小值 } } cout << ans << endl; return 0; }
原文：https://www.cnblogs.com/elisa02/p/13324400.html