Codeforces Round #380 (Div. 2) D. Sea Battle 贪心+构造

Source

Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 2)

My Solution

题意：给定了一些区间，选一些区间里的点，要求至少有一个点在其中可能存在的一条线段上。

贪心+构造

首先处理出那些能够放下长为b的线段的区间，并用sum记录好，这些区间最多可以放多少个长为b的线段。

然后由于已知有a个线段分布在这些区间里，所以 可以选 res = sum - a + 1个点，来命中至少一个线段。

que.front().first += b 就是选入的第一个点，然后每次如果还放得下一个线段则在间隔为b的下一个点选入

故选这res个点即可至少命中一条线段。

复杂度 O(n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int maxn = 1e6 + 8;

queue que;
queue ans;

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 2;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, a, b, k, sum = 0;
    string s;
    cin >> n >> a >> b >> k;
    cin >> s;
    int l = 0;
    for(int i = 0; i < n; i++){ if(s[i] == '1'){ if(i - l >= b){

                que.push(ii(l, i));
                sum += (i - l) / b;
            //cout << sum << " "; } l = i + 1; } } if(s[n-1] == '0'){ if(n - l >= b){
            que.push(ii(l, n));
            sum += (n - l) / b;
        }
    }

    int res = sum - a + 1;
    while(res--){
        if(que.front().second - que.front().first < b) que.pop();
        que.front().first += b;
        ans.push(que.front().first);
    }
    cout << ans.size() << endl;
    cout << ans.front();
    ans.pop();
    while(!ans.empty()){
        cout << " " << ans.front();
        ans.pop();
    }

    #ifdef LOCAL
    while(!que.empty()) que.pop();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx