[51Nod]1065 最小正子段和

一道蛮不错的题

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

暴力思路

很容易想到的思路是，O(N^2)的对每个i和j做差即可求

优化思路1

优化的思路是：

1. 读取的时候直接计算保留前缀和
2. 对前缀和进行排序
3. 对相邻大小前缀和，判断是否可以构成子段

具体来说就是，读入 1 -2 3 5 -2五个数字
保留前缀和(括号外为前缀和， 括号内为该前缀和为第x个数对应的前缀和，0为额外添加的值)

0(0)   1(1)   -1(2)   2(3)   7(4)   5(5)

前缀和进行排序

-1(2)   0(0)   1(1)   2(3)   5(5)   7(4)

以下索引 i ~ j 指的是 ( i , j ] 范围
对于-1和0，索引为2~0，不合法，忽略
对于0和1，索引为0~1，合法，差值为1
对于1和2，索引为1~3，合法，差值为1
对于2和5，索引为3~5，合法，差值为3
对于5和7，索引为5~4，不合法，忽略
所以最终我们得到最小正子段和1，有两个这样的正子段，分别是①第1个数；②第2个数-第3个数

整个过程中的算法复杂度为
读取过程O(N)
排序过程O(NlogN) -- 此处采用快排进行排序
两两对比过程O(N)

优化思路2

思路1存在问题，即当有多个相同前缀和时，算法复杂度可能上升
举例，输入1 -1 1 -1 1 -1共6个数字，
计算前缀和并排序：

前缀和：
0(0)   1(1)   0(2)   1(3)   0(4)   1(5)   0(6)
排序后前缀和：（排序结果可能随算法变化）
0(0)   0(2)   0(6)   0(4)   1(1)   1(5)   1(3)

此时我们发现，对于0和1两个前缀和，我们需要对比4*3 = 12次，算法复杂度变为O(N^2)，为了消除这一情况，进行同前缀和的合并，记录索引最小值及最大值，上述情况的合并结果为：

0(0,6)   1(1,5)

其中括号外仍然为前缀和，括号内第一个数为前缀和的最小索引，第二个数为前缀和的最大索引。
每次比较时只需要比较后一个前缀和的最大索引是否大于前一个前缀和的最小索引即可。

优化思路3

由于博主不太擅长堆排，因此没有采用这一优化继续优化。
采用堆排的好处是在排序过程中，就可以进行优化思路2中的合并，因为整道题对于同前缀和实际上是不要求顺序的。因此堆排的算法复杂度为O(NlogN + k)

具体代码

#include<iostream>

using namespace std;

// 存储数据
// sum[i][0]为前缀和的值
// sum[i][1]为前缀和最小索引
// sum[i][2]为前缀和最大索引
long long sum[50024][3];
long long max(long long a, long long b){
    return a > b ? a : b;
}
// 正数最小值 
long long min(long long a, long long b){
    if(a < 0) return b;
    return a < b ? a : b;
}
// 快排对前缀和排序
void sort(int left, int right){
    if(left >= right) return;
    int i = left;
    int j = right;
    long long k = sum[left][0];
    long long k2 = sum[left][1];
    
    while(i < j){
        while(i < j && sum[j][0] >= k){
            j--;
        }
        sum[i][0] = sum[j][0];
        sum[i][1] = sum[j][1];
        while(i < j && sum[i][0] <= k){
            i++;
        }
        sum[j][0] = sum[i][0];
        sum[j][1] = sum[i][1];
    }
    sum[i][0] = k;
    sum[i][1] = k2;
    
    sort(left, i - 1);
    sort(i + 1, right);
    return;
}
// 合并同前缀和
int cut(int n){
    long long cur = sum[0][0];
    int numl, numr;
    int count = 0;
    for(int i = 0; i <= n; i++){
        if(i && cur == sum[i][0]){
            numl = min(numl, sum[i][1]);
            numr = max(numr, sum[i][1]);
            sum[count - 1][1] = numl;
            sum[count - 1][2] = numr;
        }
        else{
            sum[count][0] = sum[i][0];
            sum[count][1] = sum[i][1];
            sum[count][2] = sum[i][1];
            cur = sum[i][0];
            numl = numr = sum[i][1];
            count++;
        }
    }
    return count;
}
// 打印函数，用来调试
void paint(int n){
    for(int i = 0; i < n; i++){
        cout << i << "--" << sum[i][0] << " " << sum[i][1] << " " << sum[i][2] << endl;
    }
    cout << endl;
}
int main(){
    int n;
    long long num;
    long long res = -1;
    cin >> n;
    // 读取过程空出0位，用来保存额外的辅助0
    for(int i = 0; i < n; i++){
        cin >> num;
        sum[i + 1][0] = sum[i][0] + num;
        sum[i + 1][1] = i + 1;
    }
    sum[0][2] = -1;
//  paint(n);
    // 对前缀和排序 
    sort(0, n);
//  paint(n);
    // 删去前缀和中的重复数字 
    n = cut(n);
//  paint(n);
    // 临近作差 
    for(int i = 1; i < n; i++){
        if(sum[i][2] > sum[i - 1][1]){
            res = min(res, sum[i][0] - sum[i - 1][0]);
        }
    }
    cout << res << endl;
    return 0;
}