CFR 660 C. Hard Process ( Binary Search )

Problem - 660C - Codeforces
題意：
給 0, 1 組成的序列，求修改至多 K 個數字之後的最長連續 1 子序列長度，及整體長相。
解法：
預處理前綴和，接著二分搜答案。每次確認答案是否對只需要 O( N )。

int N, K;
vi A;

void init(){
    cin >> N >> K;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

vi pA;

void preprocess(){
    pA = vi( N + 1 );
    for( int i = 0; i < N; ++i )
        pA[ i + 1 ] = pA[ i ] + !A[ i ];
}

void solve(){
    int lb = 0, ub = N;
    int ans = -1;
    while( lb <= ub ){
        int mid = lb + ub >> 1;

        int ok = 0;
        for( int i = mid; i <= N; ++i )
            if( pA[ i ] - pA[ i - mid ] <= K )
                ok = 1;

        if( ok )
            ans = mid, lb = mid + 1;
        else
            ub = mid - 1;
    }
    cout << ans << endl;
    for( int i = ans; i <= N; ++i )
        if( pA[ i ] - pA[ i - ans ] <= K ){
            for( int j = 0; j < i - ans; ++j )
                cout << A[ j ] << " ";
            for( int j = i - ans; j < i; ++j )
                cout << 1 << " ";
            for( int j = i; j < N; ++j )
                cout << A[ j ] << " ";
            return;
        }
}