当前位置: 首页 > news >正文

2024HBCPC:C Goose Goose Duck

题目描述

Iris 有 n n n 个喜欢玩鹅鸭杀的朋友,编号为 1 ∼ n 1∼n 1n。 假期的时候,大家经常会在群里问有没有人玩鹅鸭杀,并且报出现在已经参与的人数。 但是每个人对于当前是否加入游戏都有自己的想法。 具体的来说,对于第 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(1n106),表示总人数。 接下来 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(0li,ri106),含义见题目描述。

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")
#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;
}

相关文章:

2024HBCPC:C Goose Goose Duck

题目描述 Iris 有 n n n 个喜欢玩鹅鸭杀的朋友&#xff0c;编号为 1 ∼ n 1∼n 1∼n。 假期的时候&#xff0c;大家经常会在群里问有没有人玩鹅鸭杀&#xff0c;并且报出现在已经参与的人数。 但是每个人对于当前是否加入游戏都有自己的想法。 具体的来说&#xff0c;对于第…...

Llama 3 模型家族构建安全可信赖企业级AI应用之使用 Llama Guard 保护大模型对话 (八)

LlaMA 3 系列博客 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;一&#xff09; 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;二&#xff09; 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;三&#xff09; 基于 LlaMA…...

《一地霜白》读书笔记

1.3.6 街灯明灭&#xff0c;勾缀成行&#xff0c;为了生者与死者 “很多年过去了。回头看&#xff0c;沿着一排暗中的街灯&#xff0c;两三盏灭了&#xff0c;郁闷中有意外的欣喜&#xff1a;街灯明灭&#xff0c;勾缀成行&#xff0c;为了生者与死者。” 童年、青少年在人的…...

在Java中实现多线程之间的通信

一、技术难点 在Java中实现多线程之间的通信是一个复杂但重要的任务&#xff0c;它涉及到线程同步、数据共享和线程间协作等多个方面。以下是实现多线程通信时可能遇到的一些技术难点&#xff1a; 线程同步&#xff1a;多线程环境下&#xff0c;多个线程可能同时访问和修改共享…...

Python中的json.dump与json.dumps对比

Python中的json.dump与json.dumps对比 json.dumps()json.dump() json.dumps() dumps 是 “dump string” 的缩写。它将Python对象转换&#xff08;序列化&#xff09;为JSON格式的字符串。数据被转换为一个字符串&#xff0c;并且这个字符串可以直接被写入文件、发送到网络&am…...

【从零开始学习RabbitMQ | 第二篇】如何确保MQ的可靠性和消费者可靠性

目录 前言&#xff1a; MQ可靠性&#xff1a; 数据持久化&#xff1a; Lazy Queue&#xff1a; 消费者可靠性&#xff1a; 消费者确认机制&#xff1a; 消费失败处理&#xff1a; MQ保证幂等性&#xff1a; 方法一&#xff1a; 总结&#xff1a; 前言&#xff1a; …...

常用批处理命令及批处理文件编写技巧

一常用批处理命令 1.查看命令用法&#xff1a;命令 /? //如&#xff1a;cd /? 2.切换盘符目录&#xff1a;cd /d D:\test 或直接输入 d: //进入上次d盘所在的目录 3.切换目录&#xff1a;cd test 4.清屏:cls 5.“arp -a” //它会列出当前设备缓存中的所有…...

android NetworkMonitor记录

是否能上网的状态 上网url地址的设置&#xff1a; NetworkMonitor.java makeCaptivePortalHttpsUrls config_captive_portal_https_urls DEFAULT_CAPTIVE_PORTAL_HTTPS_URLS http准备监测 isCaptivePortal sendHttpAndHttpsParallelWithFallbackProbes httpsProbe.start();…...

OSPF优化——OSPF减少LSA更新量2

二、特殊区域——优化非骨干区域的LSA数量 不是骨干区域、不能存在虚链路 1、不能存在 ASBR 1&#xff09;末梢区域 该区域将拒绝 4、5LSA的进人&#xff0c;同时由该区域连接骨干0区域的ABR 向该区域&#xff0c;发布一条3类的缺省路由; 该区域内每台路由器均需配置&#xf…...

【AMS】Android 8.0+ 绕开启动后台Service限制

一、背景 应客户要求,需要在开机时,拉起应用A。但因为开机时,同时被拉起的应用过多,导致Launcher在开机那一刻较为卡顿。为解决这一问题,采取了延迟拉起的做法。在开机后,延迟一定时间,由系统服务,拉起应用A。 于是乎,就出现这么个报错: Not allowed to start ser…...

【多态】(超级详细!)

【多态】&#xff08;超级详细&#xff01;&#xff09; 前言一、 多态的概念二、重写1. 方法重写的规则2. 重写和重载的区别 三、多态实现的条件四、 向上转型五、动态绑定 前言 面向对象的三大特征&#xff1a;封装性、继承性、多态性。 extends继承或者implements实现&…...

vue的组件化

vue的组件化 vue的组件化&#xff0c;就是根据功能、业务逻辑、数据流向等因素进行划分把页面拆分成多个组件。组件是资源独立的&#xff0c;组件也可以相互嵌套。目的是提高代码的可读性、可维护性和可复用性。 组件化思想体现 ​ 组件封装步骤 1.公共组件 公共组件全局注…...

spark的简单学习一

一 RDD 1.1 RDD的概述 1.RDD&#xff08;Resilient Distributed Dataset&#xff0c;弹性分布式数据集&#xff09;是Apache Spark中的一个核心概念。它是Spark中用于表示不可变、可分区、里面的元素可并行计算的集合。RDD提供了一种高度受限的共享内存模型&#xff0c;即RD…...

【第5章】SpringBoot整合Druid

文章目录 前言一、启动器二、配置1.JDBC 配置2.连接池配置3. 监控配置 三、配置多数据源1. 添加配置2. 创建数据源 四、配置 Filter1. 配置Filter2. 可配置的Filter 五、获取 Druid 的监控数据六、案例1. 问题2. 引入库3. 配置4. 配置类5. 测试类6. 测试结果 七、案例 ( 推荐 )…...

力扣654. 最大二叉树

Problem: 654. 最大二叉树 文章目录 题目描述思路复杂度Code 题目描述 思路 对于构造二叉树这类问题一般都是利用先、中、后序遍历&#xff0c;再将原始问题分解得出结果 1.定义递归函数build&#xff0c;每次将一个数组中的最大值作为当前子树的根节点构造二叉树&#xff1b;…...

基于Netty实现WebSocket客户端

本文是基于Netty快速上手WebSocket客户端&#xff0c;不涉及WebSocket的TLS/SSL加密传输。 WebSocket原理参考【WebSocket简介-CSDN博客】&#xff0c;测试用的WebSocket服务端也是用Netty实现的&#xff0c;参考【基于Netty实现WebSocket服务端-CSDN博客】 一、基于Netty快速…...

homebrew安装mysql的一些问题

本文目录 一、Homebrew镜像安装二、mac安装mysql2.1、修改mysql密码 本文基于mac环境下进行的安装 一、Homebrew镜像安装 Homebrew国内如何自动安装&#xff0c;运行命令/bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)" 会…...

产线问题排查

CPU过高 使用top命令查看占用CPU过高的进程。 导出CPU占用高进程的线程栈。 jstack pid >> java.txt Java 内存过高的问题排查 1.分析OOM异常的原因&#xff0c;堆溢出&#xff1f;栈溢出&#xff1f;本地内存溢出&#xff1f; 2.如果是堆溢出&#xff0c;导出堆dump&…...

华为WLAN实验继续-2,多个AP如何部署

----------------------------------------如果添加新的AP&#xff0c;如何实现多AP的服务----------- 新增加一个AP2启动之后发现无法获得IP地址 在AP2上查看其MAC地址&#xff0c;并与将其加入到AC中去 打开AC&#xff0c;将AP2的MAC加入到AC中 sys Enter system view, re…...

手把手教你写Java项目(1)——流程

个人练手项目的一般流程&#xff1a; 个人练手项目的流程通常相对简单和灵活&#xff0c;但仍然遵循一定的步骤来确保项目的顺利进行。流程相对较为详细&#xff0c;不是所有流程都要实现&#xff0c;一些仅供参考。主要是让大家对项目有初步的了解&#xff0c;不至于无法入手…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

使用 uv 工具快速部署并管理 vLLM 推理环境

uv&#xff1a;现代 Python 项目管理的高效助手 uv&#xff1a;Rust 驱动的 Python 包管理新时代 在部署大语言模型&#xff08;LLM&#xff09;推理服务时&#xff0c;vLLM 是一个备受关注的方案&#xff0c;具备高吞吐、低延迟和对 OpenAI API 的良好兼容性。为了提高部署效…...

[10-1]I2C通信协议 江协科技学习笔记(17个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17...

华为云Flexus+DeepSeek征文 | MaaS平台避坑指南:DeepSeek商用服务开通与成本控制

作者简介 我是摘星&#xff0c;一名专注于云计算和AI技术的开发者。本次通过华为云MaaS平台体验DeepSeek系列模型&#xff0c;将实际使用经验分享给大家&#xff0c;希望能帮助开发者快速掌握华为云AI服务的核心能力。 目录 作者简介 前言 一、技术架构概览 1.1 整体架构设…...

RocketMQ 客户端负载均衡机制详解及最佳实践

延伸阅读&#xff1a;&#x1f50d;「RocketMQ 中文社区」 持续更新源码解析/最佳实践&#xff0c;提供 RocketMQ 专家 AI 答疑服务 前言 本文介绍 RocketMQ 负载均衡机制&#xff0c;主要涉及负载均衡发生的时机、客户端负载均衡对消费的影响&#xff08;消息堆积/消费毛刺等…...

SpringCloud——Nacos

1、核心功能&#xff1a; 服务注册与发现&#xff1a; 服务实例可动态注入到Nacos中&#xff0c;消费者通过服务名发现可用实例。 // 启用EnableDiscoveryClient注解启用Nacos SpringBootApplication EnableDiscoveryClient public class UserServiceApplication {public st…...