hiho-[Offer收割]编程练习赛65-题目2 : 最长子段

题目链接:https://hihocoder.com/problemset/problem/1769

题意

给定一个数组a[1..n]，你需要选一个尽可能长的非空连续子段，使得这个子段的和小于等于给定的一个数 S.

解法

sum[i]数组维护前缀和，mas[i]数组维护以i结尾的最大的sum[i]+S：mas[i] = max(sum[i] + s, mas[i-1])
遍历所有的sum[i]，并在mas[0]到mas[i]中lower_bound查找，假设查找结果下表为index，由于mas[index]为最大的sum[index]+S，且大于等于sum[i]，那么可以的出sum[i] - mas[index] <= 0，及就是sum[i] - sum[index] <= S，且最大。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200005;
using ll = long long;
ll a[N], sum[N], mas[N];
int main() {
    int n;
    ll s;
    cin>>n>>s;
    sum[0] = 0;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        sum[i] = sum[i-1] + a[i];
    }
    for(int i=1; i<=n; i++) {
        mas[i] = max(sum[i] + s, mas[i-1]);
    }
    int ans = -1;
    for(int i=1; i<=n; i++) {
        int pos = lower_bound(mas, mas + i, sum[i]) - mas;
        if(pos < i) {
            ans = max(ans, i - pos);
        }
    }
    cout<<ans<<endl;
    return 0;
}