51nod 1065 最小正子段和 前缀和+贪心

1065 最小正子段和

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 10 分
6.  
7. 2级题

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

分析：

我们先对前缀和进行排序，前缀和从小到大，相邻两个的如果满足sum[i].index > sum[i-1].index，相邻两个肯定是最小的。找到满足正数的最小值即可

#include<bits/stdc++.h>
using namespace std;
using namespace std;
#define N 200005
typedef long long ll;
int n;
ll a[N];
struct Node
{ll val;int index;
};
Node sum[N];int cmp(Node a,Node b)
{return a.val < b.val;
}int main()
{while(cin >> n){for(int i = 1; i <= n; i++){cin >> a[i];}sum[0].val = 0;sum[0].index = 0;for(int i = 1; i <= n; i++){sum[i].val = sum[i-1].val + a[i];sum[i].index = i;}ll min_sum = 1e18;sort(sum,sum+n+1,cmp);for(int i = 1; i <= n; i++){if(sum[i].index > sum[i-1].index){ll tmp = sum[i].val - sum[i-1].val;if(tmp>0)//可能有0min_sum =min(min_sum,tmp);}}cout << min_sum << endl;}return 0;
}