当前位置: 首页 > 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上。 一般…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...