题干:

N个整数组成的序列a11,a22,a33,…,ann,从中选出一个子序列(aii,ai+1i+1,…ajj),使这个子序列的和>0,并且这个和是所有和>0的子序列中最小的。

例如:4,-1,5,-2,-1,2,6,-2。-1,5,-2,-1,序列和为1,是最小的。

Input

第1行:整数序列的长度N(2 <= N <= 50000) 
第2 - N+1行:N个整数

Output

输出最小正子段和。

Sample Input

8
4
-1
5
-2
-1
2
6
-2

Sample Output

1

题目大意:

  中文题不解释啦。

解题报告:

    法一:可以用结构体保存一个前缀和,然后对前缀和排序,可以证明,答案就在相邻的两个排序中。当然,要满足输入顺序不能改变,即node[i].pos > node[i-1].pos && node[i].sum > node[i-1].sum  这两个条件都需要满足。并且 这里pos放在结构体里,并且带着这个pos排序,不能求完前缀和然后用pos数组存sum[i]出现的位置,因为可能有多个sum[i]是同一个值,会重叠,而且此法不能去重,所以需要带着pos这个值排序。 还有一个细节,这里的排序必须从node开始排序而不是node+1  !也很好理解,因为答案也可能就是输入的sum[i]前缀和,所以sum[i] - sum[0]也可能是答案啊!还有就是,注意这题需要longlong。

   法二:可以用线段树。

 

附一个题解:

将前n项和求出来并排序,然后比较相邻两项其位置关系,如果可以组成序列,则说明其可能是所要求结果,然后从所有可能是结果的结果中取出最小值即可。 
如:

排序前

sum 4 3 8 6 5 7 13 11
pos 1 2 3 4 5 6 7 8

排序后

sum 3 4 5 6 7 8 11 13
pos 2 1 5 4 6 3 8 7

如果ABC为排序后的结果,那么当A和B不能组成序列,而A和C可以组成序列时,那么B和C一定可以组成序列,并且BC一定会比AC更优。链接

AC代码:(前缀和排序)

#include<bits/stdc++.h>
using namespace std;
const int MAX =  50000 + 5;
int a[MAX];
int n;
struct Node {
    int pos,val;
    long long sum;
} node[MAX];
bool cmp(Node a,Node b){
    return a.sum < b.sum;
}
int main()
{
    cin>>n;
    for(int i = 1; i<=n; i++) {
        scanf("%d",&node[i].val);
        node[i].pos = i;
        node[i].sum = node[i-1].sum + node[i].val;
    }
// for(int i = 1; i<=n; i++) {
//        printf("%d  %d  %d   %d\n",i,node[i].pos,node[i].sum,node[i].val);
//    }
 //   printf("\n");
    sort(node,node+n+1,cmp);
//    for(int i = 1; i<=n; i++) {
//        printf("%d  %d  %d   %d\n",i,node[i].pos,node[i].sum,node[i].val);
//    }
    long long minn = 0x3f3f3f3f3f3f3f3f;
    int flag = 1;
    int pos = 1;
    while(node[pos].pos < node[pos - 1].pos) pos++;

    for(int i = 1; i<=n; i++) {
        if(node[i].pos > node[i-1].pos && node[i].sum > node[i-1].sum) {
            minn = min(minn,node[i].sum - node[i-1].sum);
        }

    }


    printf("%lld\n",minn);
    return 0 ;
}

法二:用set维护一下。