题目大意：
给你一个数组a，找到最大连续段[ l , r ] [l,r][l,r]:
a l + a l + 1 + . . . + a r + s > = 0 al+al+1+...+ar+s>=0al+al+1+...+ar+s>=0 (条件1)
a l + a l + 1 + . . . + a r + s < 0 al+al+1+...+ar+s<0al+al+1+...+ar+s<0 (条件2)
或者l 到 n 都 满 足 a l + a l + 1 + . . . + a n + s > = 0 l到n都满足al+al+1+...+an+s>=0l到n都满足al+al+1+...+an+s>=0
如果找不到a l + a l + 1 + . . . + a r + s > = 0 al+al+1+...+ar+s>=0al+al+1+...+ar+s>=0，则输出-1。
1.双指针算法：
结论：如果a l + a l + 1 + . . . + a r − 1 + s > = 0 ， al+al+1+...+ar-1+s>=0，al+al+1+...+ar−1+s>=0，a l + a l + 1 + . . . + a r + s < 0 al+al+1+...+ar+s<0al+al+1+...+ar+s<0,那么以l ll为左端点的满足条件一最大连续子段为:
[ l , r − 1 ] [l,r-1][l,r−1],l ll对答案的贡献已经到头了！记录下来l , r l,rl,r
接下来
所以我们只需要将l ll的指针向右移一位：看看以l + 1 l+1l+1为左端点的区间[ l + 1 , r ] [l+1,r][l+1,r]，是不是能满足条件1
1..如果能，以l + 1 l+1l+1为左端点移动 r rr 的指针向右找满足条件1的最大位置，记录下来。
2.如果不能，继续移动左指针，找到满足条件一的即可，中间的那些点就算有右端点小于r的区间满足条件一，对答案的贡献也小于原先的区间[ l , r − 1 ] [l,r-1][l,r−1]，所以等于对答案没有贡献，直接跳过就行了
如果此时的左指针指向的数和右指针指向的数满足条件一，则往后移右指针更新答案。
代码如下：
#include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) typedef pair<int, int> PII; #define ll long long #define endl "\n" #define LOCAL #define pb push_back const int N = 2e5 + 10, INF = 0x3f3f3f3f; ll qpow(int a, int b) { ll ans = 1; while (b) { if (b & 1) ans = ans * a; a = (ll)a * a; b >>= 1; } return ans; } inline int read() { int X = 0; bool flag = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') flag = 0; ch = getchar(); } while (ch >= '0' && ch <= '9') { X = (X << 1) + (X << 3) + ch - '0'; ch = getchar(); } if (flag) return X; return ~(X - 1); } inline void write(int X) { if (X < 0) { X = ~(X - 1); putchar('-'); } if (X > 9) write(X / 10); putchar(X % 10 + '0'); } //有效代码---------------------------------------------------------------------- int n, s; ll a[N]; void solve() { n = read(); s = read(); ll ans = 0; ll sum = s; int l = 0, r = 0; rep(i, 1, n) { a[i] = read(); } int j = 1; for (int i = 1; i <= n; i++) { sum += a[i]; while (j <= i && sum < 0) { sum -= a[j]; j++; } if (sum >= 0) { if (ans < i - j + 1) { ans = i - j + 1; r = i; l = j; } } } if (l != 0 && r != 0) { printf("%d %d\n", l, r); } else { cout << -1 << endl; } } //有效代码----------------------------------------------------------------------------- int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int T = 1; scanf("%d", &T); while (T--) { solve(); } return 0; }
2.线段树写法
线段树维护区间[ l , r ] [l,r][l,r]的最小前缀和
如果[l,r]区间可行满足条件一，那么，向后找最大的满足条件的r（二分）
如果[l,r]区间不满足可行条件，l指针向左移，继续找答案
那么什么时候可行呢？
如果[l,r]区间的最小的前缀和sum[x] (x属于[l,r])，sum[x]-sum[l-1]+s>=0,那么这个区间[l,r]肯定满足sum[r]-sum[l-1]+s>=0,因为sum[r]>=sum[x],所以区间[l,r]满足条件一
如果sum[x]-sum[l-1]+s<0,那么[l,x]区间不满足条件一，那么[l,r]区间肯定也不满足，因为r>=x.
所以证明完毕，代码如下：
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long LL; const int N = 2e5 + 10; const LL INF = 1e15; int n, s; LL sum[N]; struct node { int l; int r; LL p; } tr[N << 2]; void build(int u, int l, int r) { tr[u].l = l; tr[u].r = r; if (l == r) { tr[u].p = sum[l];//线段树维护前缀和 return; } int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); tr[u].p = min(tr[u << 1].p, tr[u << 1 | 1].p); } LL query(int u, int l, int r) //找区间[l,r]的最小前缀和 { if (tr[u].l >= l && tr[u].r <= r) { return tr[u].p; } int mid = tr[u].r + tr[u].l >> 1; LL mi = 1e15; if (l <= mid) mi = min(query(u << 1, l, r), mi); if (r > mid) mi = min(query(u << 1 | 1, l, r), mi); return mi; } bool check(int l, int r) { if (query(1, l, r) - sum[l - 1] + s >= 0) return true; return false; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &s); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); sum[i] = sum[i - 1] + x; } build(1, 1, n); int ans = 0; int ll = 0, rr = 0; for (int i = 1; i <= n; i++) { int l = i, r = n; while (l < r)//找最大的mid（r） { int mid = l + r + 1 >> 1; if (check(i, mid)) l = mid; else r = mid - 1; } if (check(i, l) && ans < (l - i + 1))//检查[i,l]区间是否合格 { ans = l - i + 1; ll = i; rr = l; } } if (ans) { cout << ll << ' ' << rr << "\n"; } else { cout << -1 << "\n"; } } return 0; }
