51nod 1065 最小正子段和

题目网址：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

样例输出

二、解题思路

这道题我们可以利用前缀和+结构体排序来解决

首先，大家来看一下：我们假设我们先把所有数字的前缀和都求出来了

（拿样例来举例）

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