$CF1141B Maximal Continuous Rest$

告诉你一天n件事情

a[i]为1是休息 a[i]为2是工作

求最长连续的休息时间（即最长的1

可以作为环状来求。(即环状最长的1

这题就可以用前缀和贪心等什么操作。。

然后用$ans1ans2$瞎搞

#include <bits/stdc++.h>

using namespace std;

typedef long long LL ;

inline LL In() { LL res(0),f(1); register char c ;

    while(isspace(c=getchar())) ; c == '-'? f = -1 , c = getchar() : f = 1 ;

    while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ; return res * f ;

}

int n ;

int a[200000+5] ;

int cnt[200000+5] ;

int flag = 1 ;

int ans = 0 ;

int ans1 = 0 ;

int ans2 = 0 ;

signed main() {

    n = In() ;

    for(register int i=1;i<=n;i++) a[i] = In() ;//读入

    for(register int i=1;i<=n;i++)

    if(a[i]==1) cnt[i]=cnt[i-1]+1,ans1=max(ans1,cnt[i]);//求前缀和 即当前最长的1 ans1储存最大值

    else {

        if(flag) ans2+=(i-1),flag=0;//储存最前面的一段1

        cnt[i]=0;

    }

    if(cnt[n]) ans = cnt[n] + ans2;//如果第n个位置有连在一起的。

//则数字为 cnt[n]+ans2

    cout << max(ans,ans1) << endl ;//ans求的是序列中最大值。 ans是首尾环状。 要求的是最长的则取max

    return 0 ;

}

巴特西

$CF1141B Maximal Continuous Rest$

最新文章

热门文章