b_aw_区间（贪心）

给定 n 个区间 [ai,bi]和 n 个整数 ci。
你需要构造一个整数集合 Z，使得?i∈[1,n],Z 中满足ai≤x≤bi的整数 x 不少于 ci 个。
求这样的整数集合 Z 最少包含多少个数。

思路
对所有线段按右端点升序排列，因为在满足条件的情况下，尽量放后面的数"容错能力"更强

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct node {
    int l,r,c;
} A[N];
bool cmp(node& a, node& b) {
    return a.r<b.r;
}
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,ans=0,vis[n+1]; cin>>n;
    memset(vis, false, sizeof vis);
    for (int i=0; i<n; i++) cin>>A[i].l>>A[i].r>>A[i].c;
    sort(A, A+n, cmp);

    for (int i=0; i<n; i++) {
        int l=A[i].l, r=A[i].r, need=A[i].c;
        for (int j=l; j<=r; j++) if (vis[j]) need--; //如果已经放了数，则需求-1
        if (need>0) for (int j=r; j>=l && need>0; j--) if (!vis[j]) {
            need--, vis[j]=1, ans++;
        }
    }
    cout<<ans;
    return 0;
}

b_aw_区间（贪心）

原文：https://www.cnblogs.com/wdt1/p/13724927.html