題干：

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項和求出來并排序，然后比較相鄰兩項其位置關系，如果可以組成序列，則說明其可能是所要求結果，然后從所有可能是結果的結果中取出最小值即可。?
如：

排序前

sum4386571311

pos	1	2	3	4	5	6	7	8

排序后

sum3456781113

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維護一下。?

?

總結

以上是生活随笔為你收集整理的【51nod - 1065】 最小正子段和（ 前缀和排序 ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。