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

【DS思想+堆贪心】CF595div3 D2

Problem - D2 - Codeforces

题意:

 

 思路:

大家都说这是典,但是我不懂怎么个典法,可能堆贪心都是这样做的吗,不懂

首先肯定要贪心,对于一个坏点,优先删除覆盖别的点多的

考虑nlogn做法,先去枚举点,然后把覆盖该点的所有区间扔进优先队列里,优先删除右端点靠右的

那怎么看是不是坏点,还得维护一个差分数组,边枚举边维护

感觉突破点就是堆贪心

Code:

#include <bits/stdc++.h>#define int long longusing i64 = long long;constexpr int N = 2e5 + 10;
constexpr int M = 1e6 + 10;
constexpr int P = 2600;
constexpr i64 Inf = 1e18;
constexpr int mod = 998244353;
constexpr double eps = 1e-6;struct ty {int l, r;int id;bool operator < (const ty & a) const {return a.r > r;}
}p[N];std::priority_queue<ty> q;int n, k;
int sum[N];
int ans[N];bool cmp(ty x, ty y) {if (x.l == y.l) return x.r < y.r;return x.l < y.l;
}
void solve() {std::cin >> n >> k;for (int i = 1; i <= n; i ++) {std::cin >> p[i].l >> p[i].r;p[i].id = i;sum[p[i].l] ++;sum[p[i].r + 1] --;}std::sort(p + 1, p + 1 + n, cmp);int j = 1;int len = 0;for (int i = 1; i < N; i ++) {while (j <= n && p[j].l <= i) q.push(p[j ++]);sum[i] += sum[i - 1];while (sum[i] > k) {auto u = q.top();q.pop();ans[++len] = u.id;sum[i] --;sum[u.r + 1] ++;}}std::cout << len << "\n";for (int i = 1; i <= len; i ++) std::cout << ans[i] << " \n" [i == len];
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while (t--) {solve();}return 0;
}

相关文章:

【DS思想+堆贪心】CF595div3 D2

Problem - D2 - Codeforces 题意&#xff1a; 思路&#xff1a; 大家都说这是典&#xff0c;但是我不懂怎么个典法&#xff0c;可能堆贪心都是这样做的吗&#xff0c;不懂 首先肯定要贪心&#xff0c;对于一个坏点&#xff0c;优先删除覆盖别的点多的 考虑nlogn做法&#x…...

2023-09-08 LeetCode每日一题(计算列车到站时间)

2023-09-08每日一题 一、题目编号 2651. 计算列车到站时间二、题目链接 点击跳转到题目位置 三、题目描述 给你一个正整数 arrivalTime 表示列车正点到站的时间&#xff08;单位&#xff1a;小时&#xff09;&#xff0c;另给你一个正整数 delayedTime 表示列车延误的小时…...

软考-高级-信息系统项目管理第四版(完整24章全笔记)

《信息系统项目管理师教程》&#xff08;第4版&#xff09;是由全国计算机专业技术资格考试办公室组织编写的考试用书&#xff0c;根据2022年审定通过的《信息系统项目管理师考试大纲》编写&#xff0c;对信息系统项目管理师岗位所要求的主要知识及应用技术进行了阐述。 《信息…...

华为Mate 60和iPhone 15选哪个?

最近也有很多朋友问我这个问题来着&#xff0c;首先两款手机定位都是高端机&#xff0c;性能和体验各有千秋&#xff0c;各自有自己的铁杆粉。 但是让人意想不到的是华为mate60近日在海外越来越受欢迎和追捧&#xff0c;甚至是引起了不少人的抢购&#xff0c;外观设计和…...

嵌入式Linux驱动开发(同步与互斥专题)(二)

一、自旋锁spinlock的实现 自旋锁&#xff0c;顾名思义&#xff1a;自己在原地打转&#xff0c;等待资源可用&#xff0c;一旦可用就上锁霸占它。 ① 原地打转的是CPU x&#xff0c;以后CPU y会解锁&#xff1a;这涉及多个CPU&#xff0c;适用于SMP系统&#xff1b; ② 对于单…...

Docker安装部署Nexus3作为内网镜像代理缓存容器镜像

Docker安装部署Nexus3作为内网镜像代理 一、背景描述 基础镜像比较小&#xff0c;仓库使用阿里云或者腾讯云拉取速度挺快&#xff0c;但是时光飞逝几年时间过去&#xff0c;再加上AI加持的情况下&#xff0c;有些镜像的大小已经接近20G&#xff01; 这种情况下不管是测试环境…...

SpringBoot工具库:解决SpringBoot2.*版本跨域问题

1.解决问题&#xff1a;When allowCredentials is true, xxxxxxx , using “allowedOriginPatterns“ instead 2.3版本跨域配置如下 /*** 跨域问题解决*/ Configuration public class CorsConfig implements WebMvcConfigurer {Overridepublic void addCorsMappings(CorsRegi…...

docker安装开发常用软件MySQL,Redis,rabbitMQ

Docker安装 docker官网&#xff1a;Docker: Accelerated Container Application Development docker镜像仓库&#xff1a;https://hub.docker.com/search?qnginx 官网的安装教程&#xff1a;Install Docker Engine on CentOS | Docker Docs 安装步骤 1、卸载以前安装的doc…...

C# Unity FSM 状态机

C# Unity FSM 状态机 使用状态机可以降低代码耦合性&#xff0c;并且可以优化代码可读性&#xff0c;方便团队协作等。 对于游戏开发内容来讲游戏开发的流程控制玩家动画都可以使用FSM有限状态机来实现。 1.FsmState 每个状态的基类&#xff0c;泛型参数表示所拥有者 publi…...

pytorch搭建squeezenet网络的整套工程,及其转tensorrt进行cuda加速

本来&#xff0c;前辈们用caffe搭建了一个squeezenet的工程&#xff0c;用起来也还行&#xff0c;但考虑到caffe的停更后续转trt应用在工程上时可能会有版本的问题所以搭建了一个pytorch版本的。 以下的环境搭建不再细说&#xff0c;主要就是pyorch&#xff0c;其余的需要什么p…...

【精读Uboot】SPL阶段的board_init_r详细分析

对于i.MX平台上的SPL来说&#xff0c;其不会直接跳转到Uboot&#xff0c;而是在SPL阶段借助BOOTROM跳转到ATF&#xff0c;然后再通过ATF跳转到Uboot。 board_init_f会初始化设备相关的硬件&#xff0c;最后进入board_init_r为镜像跳转做准备。下面是board_init_r调用的核心函数…...

canvas绘制渐变色三角形金字塔

项目需求:需要绘制渐变色三角形金字塔,并用折线添加标识 (其实所有直接用图片放上去也行,但是ui没切图,我也懒得找她要,正好也没啥事,直接自己用代码绘制算了,总结一句就是闲的) 最终效果如下图: (以上没用任何图片,都是代码绘制的) 在网上找了,有用canvas绘…...

企业电子招标采购系统源码Spring Boot + Mybatis + Redis + Layui + 前后端分离 构建企业电子招采平台之立项流程图

功能模块&#xff1a; 待办消息&#xff0c;招标公告&#xff0c;中标公告&#xff0c;信息发布 描述&#xff1a; 全过程数字化采购管理&#xff0c;打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力&#xff0c;为外部供…...

Debain JDK8 安装

Debain JDK8 安装 首先请安装依赖&#xff1a; sudo apt-get update && sudo apt-get install -y wget apt-transport-https然后信任 GPG 公钥&#xff1a; wget -O - https://packages.adoptium.net/artifactory/api/gpg/key/public | sudo tee /etc/apt/keyrings/…...

Python序列操作指南:列表、字符串和元组的基本用法和操作

文章目录 序列列表创建列表访问元素修改元素添加和删除元素 range()字符串创建字符串访问字符字符串切片修改字符串 元组创建元组访问元素获取元素数量元组的特点&#xff1a; 可变对象改变对象的值改变变量的指向比较运算符总结 python精品专栏推荐python基础知识&#xff08;…...

【已更新代码图表】2023数学建模国赛E题python代码--黄河水沙监测数据分析

E 题 黄河水沙监测数据分析 黄河是中华民族的母亲河。研究黄河水沙通量的变化规律对沿黄流域的环境治理、气候变 化和人民生活的影响&#xff0c;以及对优化黄河流域水资源分配、协调人地关系、调水调沙、防洪减灾 等方面都具有重要的理论指导意义。 附件 1 给出了位于小浪底水…...

【前端】CSS-Grid网格布局

目录 一、grid布局是什么二、grid布局的属性三、容器属性1、display①、语句②、属性值 2、grid-template-columns属性、grid-template-rows属性①、定义②、属性值1&#xff09;、固定的列宽和行高2&#xff09;、repeat()函数3&#xff09;、auto-fill关键字4&#xff09;、f…...

计算机竞赛 基于深度学习的动物识别 - 卷积神经网络 机器视觉 图像识别

文章目录 0 前言1 背景2 算法原理2.1 动物识别方法概况2.2 常用的网络模型2.2.1 B-CNN2.2.2 SSD 3 SSD动物目标检测流程4 实现效果5 部分相关代码5.1 数据预处理5.2 构建卷积神经网络5.3 tensorflow计算图可视化5.4 网络模型训练5.5 对猫狗图像进行2分类 6 最后 0 前言 &#…...

2023-9-8 求组合数(二)

题目链接&#xff1a;求组合数 II #include <iostream> #include <algorithm>using namespace std;typedef long long LL; const int mod 1e9 7; const int N 100010;// 阶乘&#xff0c;阶乘的逆 int fact[N], infact[N];LL qmi(int a, int k, int p) {int res…...

k8s service的一些特性

文章目录 Service分发负载的策略同一端口通过不同协议暴露Headless Service的负载分发策略 Service分发负载的策略 大家都知道&#xff0c;一个service可以对应多个pod&#xff0c;那么一定要有一些方法来把service接收到的请求&#xff08;负载&#xff09;转发到pod上。 一般…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...