传送门

题目大意：

给一串数，又正有负，求每一个前缀都大于0的最长子串长度。

题目分析：

直接贪心：每次左端点向右推1，不断延伸右端点，更新答案。

code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

namespace IO{
    inline ll read(){
        ll i = 0, f = 1; char ch = getchar();
        for(; (ch < \'0\' || ch > \'9\') && ch != \'-\'; ch = getchar());
        if(ch == \'-\') f = -1, ch = getchar();
        for(; ch >= \'0\' && ch <= \'9\'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - \'0\');
        return i * f;
    }
    inline void wr(ll x){
        if(x < 0) putchar(\'-\'), x = -x;
        if(x > 9) wr(x / 10);
        putchar(x % 10 + \'0\');
    }
}using namespace IO;

const int N = 1e5 + 5;
int n, c[N << 1];

int main(){
    freopen("h.in", "r", stdin);
    while(~scanf("%d", &n)){
        for(int i = 1; i <= n; i++){int w = read(), l = read(); c[i] = w - l;}
        for(int i = n + 1; i <= 2 * n; i++) c[i] = c[i - n];
        int pos, sum = 0, ans = 0; pos = 1;
        for(int i = 1; i <= n; i++){
            sum -= c[i - 1];
            while(sum + c[pos] >= 0 && pos < i + n) sum += c[pos++];
            ans = max(ans, pos - i);
        }
        wr(ans), putchar(\'\n\');
    }
    return 0;
}

版权声明：本文为CzYoL原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/CzYoL/p/7668787.html