种树

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1204 字

按右端点排序，从右往左补种缺失的树

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1423
// 题意：编号 1..N 的路段，每个居民要求在区间 [B, E] 内至少种 T 棵树，求满足所有要求的最少种树数量，并输出所有树的位置。
// 思路：按区间右端点 E 升序处理每个要求。
// 1. 先数出该区间内已经种了多少棵，不够的部分再补种。
// 2. 补种时从区间最右端往左放，这样一棵树能同时照顾到后面右端点更大的区间。
// 复杂度：O(NM) 时间 / O(N) 空间
// 易错点：必须按右端点升序排序，按左端点或按输入顺序贪心都会变多种树。
// 易错点：输出位置要按编号升序排列，而贪心放置的顺序是从右往左的。
#include <bits/stdc++.h>
using namespace std;
struct Req {
    int b, e, t;
};
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    vector<Req> r(m);
    for(int i = 0; i < m; i++) cin >> r[i].b >> r[i].e >> r[i].t;
    sort(r.begin(), r.end(), [](const Req& x, const Req& y){
        return x.e < y.e;
    });
    vector<int> used(n + 2, 0);
    vector<int> pos;
    for(int i = 0; i < m; i++){
        int cnt = 0;
        for(int j = r[i].b; j <= r[i].e; j++) cnt += used[j];
        for(int j = r[i].e; j >= r[i].b && cnt < r[i].t; j--){
            if(!used[j]){
                used[j] = 1;
                pos.push_back(j);
                cnt++;
            }
        }
    }
    sort(pos.begin(), pos.end());
    cout << pos.size() << "\n";
    for(int i = 0; i < (int)pos.size(); i++){
        if(i) cout << " ";
        cout << pos[i];
    }
    cout << "\n";
    return 0;
}

种树

正文

一本通·提高篇的其它内容