org后缀做网站行,静态网站 apache,医疗网站建设公司哪家好,wordpress添加目录题目描述
Iris 有 n n n 个喜欢玩鹅鸭杀的朋友#xff0c;编号为 1 ∼ n 1∼n 1∼n。 假期的时候#xff0c;大家经常会在群里问有没有人玩鹅鸭杀#xff0c;并且报出现在已经参与的人数。 但是每个人对于当前是否加入游戏都有自己的想法。 具体的来说#xff0c;对于第…题目描述
Iris 有 n n n 个喜欢玩鹅鸭杀的朋友编号为 1 ∼ n 1∼n 1∼n。 假期的时候大家经常会在群里问有没有人玩鹅鸭杀并且报出现在已经参与的人数。 但是每个人对于当前是否加入游戏都有自己的想法。 具体的来说对于第 i i i 个人如果当前已经加入游戏的人数处于区间 [ l i , r i ] [l_i,r_i] [li,ri] 之间那 ta 就会愿意加入游戏。 你认为参与游戏的人越多游戏将会越有趣所以你决定给大家安排一个加入顺序使得加入游戏的人数最多。
Input
第一行一个整数 n ( 1 ≤ n ≤ 1 0 6 ) n (1≤n≤10^6) n(1≤n≤106)表示总人数。 接下来 n n n 行每行为两个由空格分隔的整数 l i , r i ( 0 ≤ l i , r i ≤ 1 0 6 ) l_i,r_i (0≤l_i,r_i≤10^6) li,ri(0≤li,ri≤106)含义见题目描述。
Output
第一行一个非负整数 m m m表示最多能有多少个人加入游戏。 接下来一行 m m m 个整数由空格分隔第 i i i 个数为 p i p_i pi表示第 i 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)
#includebits/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_queuenode, vectornode, decltype(cmp1) heapl(cmp1); // 左端点小的排前面priority_queuenode, vectornode, 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; // 当前参加游戏的人数vectorint 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;
}
