题目：
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个整数
输出
输出最小正子段和。
输入样例
输出样例
解法：
遍历数组处理前缀和，同时记录前缀和，在遍历到a[i]时，找到与sum[i]相差最小的位置k，并且使得sum[i] - sum[k] > 0 ，可以利用二分进行查找，总复杂度为nlogn。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #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);
}
|