CFR 738 D. Sea Battle ( Greedy )

Problem - D - Codeforces

題意：
給船的數量，船的長度，以及已嘗試射過多少位置，以及射的位置分布。地圖是一維的，而船的分佈未知。求至少還要再射多少位置，以及是哪些，才能保證至少射到一個船。

資料規模：
1 ≤ n ≤ 2e5, 1 ≤ a, b ≤ n, 0 ≤ k ≤ n - 1

解法：
求有多少區間是可能躲船的，以及分別可以藏幾隻。接著掃過去，每次貪心選最後一個位置，使得左邊都不能放船。當可藏的位置嚴格小於船的數量就退出。

時間 / 空間複雜度：
O( N )

int N, A, B, K;
string S;

void init(){
    cin >> N >> A >> B >> K;
    cin >> S;
}

vector< tuple< int, int > > len;

int get_ship( int l ){
    return l / B;
}

int shipsum;

void preprocess(){
    for( int i = 0; i < S.size(); ++i ){
        if( S[ i ] == '1' ) continue;
        int j;
        for( j = i + 1; j < S.size(); ++j )
            if( S[ j ] == '1' )
                break;
        if( j - i >= B )
            len.emplace_back( j - i, i );
        i = j;
    }
    for( int i = 0; i < len.size(); ++i )
        shipsum += get_ship( get< 0 >( len[ i ] ) );
}

void solve(){
    vector< int > ans;
    for( int i = 0, cnt = 0; i < len.size(); ++i ){
        if( shipsum - ( cnt + get_ship( get< 0 >( len[ i ] ) ) ) < A ){
            for( int j = B - 1; j < get< 0 >( len[ i ] ); j += B ){
                ans.emplace_back( get< 1 >( len[ i ] ) + j );
                ++cnt;
                if( shipsum - cnt < A )
                    break;
            }
            break;
        }
        cnt += get_ship( get< 0 >( len[ i ] ) );
        for( int j = B - 1; j < get< 0 >( len[ i ] ); j += B )
            ans.emplace_back( get< 1 >( len[ i ] ) + j );
    }
    cout << ans.size() << endl;
    for( int i = 0; i < ans.size(); ++i )
        cout << ans[ i ] + 1 << " \n"[ i + 1 == ans.size() ]; 
}