51nod 1065 最小正子段和 (O(nlogn)算法）

分析：O(n^2)算法是预处理前缀和，然后先枚举子段左端点再枚举子段右端点（两个for循环）对结果进行更新.完美超时。

　　　而实际上是没必要枚举右端点的，要想对结果更新则右端点的前缀和一定大于左端点的前缀和.所以嘛，可以对前缀和数组排个序（O(nlogn)）。

　　　这时候依旧枚举左端点，而右端点只可能是左端点加一。因为如果【i，i+1】满足要求，i+1之后的前缀和一定比i+1大，不可能再对结果有影响。而如果【i，i+1】不满足要求，那么【i，i+2】不会比【i+1，i+2】更优。

　　　这时候会有个特殊情况，如果i和i+1的前缀和相等呢？这时【i，i+1】肯定不满足要求，但【i，i+2】是可能满足的。不过既然它们前缀和相等，那么把下标小的放后面就能保证【i，i+2】不会比【i+1，i+2】更优。

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define INF 0x3f3f3f3f
 5 typedef long long ll;
 6 struct node
 7 {
 8     ll num;
 9     ll cnt;
10 };
11 node sum[50005];
12 bool cmp(const node &n1,const node&n2)
13 {
14     if(n1.cnt==n2.cnt) 
15         return n1.num>n2.num;
16     return n1.cnt<n2.cnt;
17 }
18 ll n;
19 int main()
20 {
21     ios::sync_with_stdio(false);
22     cin>>n;
23     cin>>sum[0].cnt;
24     sum[0].num=0;
25     for(ll i=1;i<n;i++)
26     {
27         cin>>sum[i].cnt;
28         sum[i].cnt+=sum[i-1].cnt;
29         sum[i].num=i;
30 
31     }
32 
33     sort(sum,sum+n,cmp);
34 
35     ll ans=INF;
36     for(ll i=0;i<n;i++)
37         if(sum[i].cnt>0)
38     {
39         ans=sum[i].cnt;
40         break;
41     }
42 
43     for(ll i=0;i<n-1;i++)
44     {
45         if(sum[i+1].cnt>sum[i].cnt && sum[i+1].num>sum[i].num)
46             ans=min(ans,sum[i+1].cnt-sum[i].cnt);
47     }
48     cout<<ans<<endl;
49     return 0;
50 }

View Code

1065 最小正子段和

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

取消关注

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，是最小的。

Input

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

Output

输出最小正子段和。

Input示例

Output示例