2024HBCPC：C Goose Goose Duck

题目描述

Iris 有 $n$ 个喜欢玩鹅鸭杀的朋友，编号为 $1\sim n$。 假期的时候，大家经常会在群里问有没有人玩鹅鸭杀，并且报出现在已经参与的人数。 但是每个人对于当前是否加入游戏都有自己的想法。 具体的来说，对于第 $i$ 个人，如果当前已经加入游戏的人数处于区间 $[l_i,r_i]$ 之间，那 ta 就会愿意加入游戏。 你认为参与游戏的人越多，游戏将会越有趣，所以你决定给大家安排一个加入顺序，使得加入游戏的人数最多。

Input

第一行，一个整数 $n(1\le n\le 10^6)$，表示总人数。 接下来 $n$ 行，每行为两个由空格分隔的整数 $l_i,r_i(0\le l_i,r_i\le 10^6)$，含义见题目描述。

Output

第一行一个非负整数 $m$，表示最多能有多少个人加入游戏。 接下来一行 $m$ 个整数，由空格分隔，第 $i$ 个数为 $p_i$，表示第 $i$ 个加入游戏的人。

若有多种加入游戏的方案，你可以输出任意一种。

输入样例

5
2 5
4 4
0 2
0 2
1 4

输出样例

5
4 3 5 1 2 

解题思路

考虑贪心，我们很容易可以想到按照左端点从小到大排序，那么对于同一人数时，有多个人可以加入游戏，应该选择右端点最小的人参加游戏，实现这个思路则是用优先队列动态维护右端点最小的人即可

正确代码

#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define debug(x) cerr << #x" = " << x << '\n';
using namespace std;void solve()
{int n;cin >> n;struct node{int l, r, i;};auto cmp1 = [](node A, node B){return A.l > B.l;};auto cmp2 = [](node A, node B){return A.r > B.r;};priority_queue<node, vector<node>, decltype(cmp1)> heapl(cmp1); // 左端点小的排前面priority_queue<node, vector<node>, decltype(cmp2)> heapr(cmp2); // 右端点小的排前面for (int i = 1; i <= n; i++){int l, r;cin >> l >> r;heapl.push({l, r, i});}int res = 0; // 当前参加游戏的人数vector<int> ans; // 答案序列while (1){// 当前参与游戏的人数达到了这个人的左端点，则把他加入到另一个堆中去while (heapl.size() && heapl.top().l == res) {heapr.push(heapl.top());heapl.pop();}if (heapr.empty()) break;  // 如果没有人可以参加游戏，则跳出死循环ans.push_back(heapr.top().i); // 把右端点最小的人加入答案序列res ++; // 参加人数+1heapr.pop(); // 如果出现右端点小于当前人数，那么这个人无法参加游戏了，则弹出while (heapr.size() && heapr.top().r < res) heapr.pop(); }cout << res << '\n';for (int i : ans) cout << i << ' ';
}signed main()
{// freopen("Sample.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;// cin >> T;while (T--) solve();return 0;
}