[题解]2024CCPC河北省赛-Goose Goose Duck

• Sources：C - Goose Goose Duck
• Abstract：有 $n$ 个人正在做游戏，其编号顺次为 $1,\dots ,n$ ，当且仅当目前有 $[l_i,r_i]$ 人加入游戏时，第 $i$ 个人会加入游戏。构造加入游戏的顺序方案，使加入游戏的总人数最大。
• Keywords：贪心，构造(签到题)
• Solution：将 $[l_i,r_i]$ 按左端点排序，顺次枚举右边界，判断合法的人，并将最早将不能加入(即$r_i$最小)的人加入即可，此处可使用堆维护。复杂度$O(n\log n)$。
• Code：

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
#define int ll
#define endl "\n"
using pii=pair<int,int>;
struct node{
    int l,r,i;
};
bool cmp(node a,node b){
    if(a.l!=b.l) return a.l<b.l;
    return a.r<b.r;
}
bool cmp1(pii a,pii b){
    if(a.first!=b.first) return a.first>b.first;
    return a.second>b.second;
}
void solve(){
    int n;cin>>n;
    vector<node>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i].l>>v[i].r;
        v[i].i=i+1;
    }
    sort(v.begin(),v.end(),cmp);
    int cnt=0;
    priority_queue<pii,vector<pii>,bool(*)(pii,pii)>pq(cmp1);
    vector<int>ans;
    for(int i=0;i<n;i++){//枚举右边界
        while(cnt<n&&v[cnt].l<=i)//先看左端点是否合法,合法的入堆
            pq.push({v[cnt].r,v[cnt].i}),cnt++;
        while(pq.size()&&pq.top().first<i)//再看右端点是否合法,不合法的出堆
            pq.pop();
        if(pq.empty())//无可行解
            break;
        ans.push_back(pq.top().second);//优先将右边界最小的人加入
        pq.pop();
    }
    cout<<ans.size()<<endl;
    for(auto i:ans) cout<<i<<' ';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int t=1;
    while(t--) solve();
    return 0;
}