题目大意：

给一串数，又正有负，求每一个前缀都大于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;

}

巴特西

HDU 1422 重温世界杯 - 贪心

题目大意：

题目分析：

code

最新文章

热门文章