题目：

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

解法：

遍历数组处理前缀和，同时记录前缀和，在遍历到a[i]时，找到与sum[i]相差最小的位置k，并且使得sum[i] - sum[k] > 0 ，可以利用二分进行查找，总复杂度为nlogn。

代码：

#include<stdio.h>
#include<set>
#include<algorithm>
using namespace std;
int a[500010];
set<long long > z;
set<long long > f;
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    long long sum = 0, ans = 9999999999;
    for(int i = 0; i < n; i++)
    {
        sum += a[i];
        long long  p = 0;
        set<long long > ::iterator it ;
        if(sum < 0){
            it = f.lower_bound(-sum);
            if(it != f.end()){
                while(it != f.end() && *it == -sum)
                    it++;
                if(it == f.end()){
                    continue;
                }
                p = *it;
            }
            f.insert(-sum);
        }
        else{
           it = z.lower_bound(-sum);
            if(it != z.end()){
                while(it != z.end() && *it == -sum)
                    it++;
                if(it == z.end()){
                    continue;
                }
                p = *it;
               
            }
            z.insert(-sum);
        }
       // for(it = z.begin(); it != z.end(); it++)
            //printf("%lld ", *it);
       // printf("\n%lld %lld\n", sum ,-p);
       if(sum + p > 0)
        ans = min(ans, sum + p);
    }
    printf("%lld\n", ans);
}