【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 题意: 思路: 大家都说这是典,但是我不懂怎么个典法,可能堆贪心都是这样做的吗,不懂 首先肯定要贪心,对于一个坏点,优先删除覆盖别的点多的 考虑nlogn做法&#x…...
2023-09-08 LeetCode每日一题(计算列车到站时间)
2023-09-08每日一题 一、题目编号 2651. 计算列车到站时间二、题目链接 点击跳转到题目位置 三、题目描述 给你一个正整数 arrivalTime 表示列车正点到站的时间(单位:小时),另给你一个正整数 delayedTime 表示列车延误的小时…...
软考-高级-信息系统项目管理第四版(完整24章全笔记)
《信息系统项目管理师教程》(第4版)是由全国计算机专业技术资格考试办公室组织编写的考试用书,根据2022年审定通过的《信息系统项目管理师考试大纲》编写,对信息系统项目管理师岗位所要求的主要知识及应用技术进行了阐述。 《信息…...
华为Mate 60和iPhone 15选哪个?
最近也有很多朋友问我这个问题来着,首先两款手机定位都是高端机,性能和体验各有千秋,各自有自己的铁杆粉。 但是让人意想不到的是华为mate60近日在海外越来越受欢迎和追捧,甚至是引起了不少人的抢购,外观设计和…...
嵌入式Linux驱动开发(同步与互斥专题)(二)
一、自旋锁spinlock的实现 自旋锁,顾名思义:自己在原地打转,等待资源可用,一旦可用就上锁霸占它。 ① 原地打转的是CPU x,以后CPU y会解锁:这涉及多个CPU,适用于SMP系统; ② 对于单…...
Docker安装部署Nexus3作为内网镜像代理缓存容器镜像
Docker安装部署Nexus3作为内网镜像代理 一、背景描述 基础镜像比较小,仓库使用阿里云或者腾讯云拉取速度挺快,但是时光飞逝几年时间过去,再加上AI加持的情况下,有些镜像的大小已经接近20G! 这种情况下不管是测试环境…...
SpringBoot工具库:解决SpringBoot2.*版本跨域问题
1.解决问题: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官网:Docker: Accelerated Container Application Development docker镜像仓库:https://hub.docker.com/search?qnginx 官网的安装教程:Install Docker Engine on CentOS | Docker Docs 安装步骤 1、卸载以前安装的doc…...
C# Unity FSM 状态机
C# Unity FSM 状态机 使用状态机可以降低代码耦合性,并且可以优化代码可读性,方便团队协作等。 对于游戏开发内容来讲游戏开发的流程控制玩家动画都可以使用FSM有限状态机来实现。 1.FsmState 每个状态的基类,泛型参数表示所拥有者 publi…...
pytorch搭建squeezenet网络的整套工程,及其转tensorrt进行cuda加速
本来,前辈们用caffe搭建了一个squeezenet的工程,用起来也还行,但考虑到caffe的停更后续转trt应用在工程上时可能会有版本的问题所以搭建了一个pytorch版本的。 以下的环境搭建不再细说,主要就是pyorch,其余的需要什么p…...
【精读Uboot】SPL阶段的board_init_r详细分析
对于i.MX平台上的SPL来说,其不会直接跳转到Uboot,而是在SPL阶段借助BOOTROM跳转到ATF,然后再通过ATF跳转到Uboot。 board_init_f会初始化设备相关的硬件,最后进入board_init_r为镜像跳转做准备。下面是board_init_r调用的核心函数…...
canvas绘制渐变色三角形金字塔
项目需求:需要绘制渐变色三角形金字塔,并用折线添加标识 (其实所有直接用图片放上去也行,但是ui没切图,我也懒得找她要,正好也没啥事,直接自己用代码绘制算了,总结一句就是闲的) 最终效果如下图: (以上没用任何图片,都是代码绘制的) 在网上找了,有用canvas绘…...
企业电子招标采购系统源码Spring Boot + Mybatis + Redis + Layui + 前后端分离 构建企业电子招采平台之立项流程图
功能模块: 待办消息,招标公告,中标公告,信息发布 描述: 全过程数字化采购管理,打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力,为外部供…...
Debain JDK8 安装
Debain JDK8 安装 首先请安装依赖: sudo apt-get update && sudo apt-get install -y wget apt-transport-https然后信任 GPG 公钥: wget -O - https://packages.adoptium.net/artifactory/api/gpg/key/public | sudo tee /etc/apt/keyrings/…...
Python序列操作指南:列表、字符串和元组的基本用法和操作
文章目录 序列列表创建列表访问元素修改元素添加和删除元素 range()字符串创建字符串访问字符字符串切片修改字符串 元组创建元组访问元素获取元素数量元组的特点: 可变对象改变对象的值改变变量的指向比较运算符总结 python精品专栏推荐python基础知识(…...
【已更新代码图表】2023数学建模国赛E题python代码--黄河水沙监测数据分析
E 题 黄河水沙监测数据分析 黄河是中华民族的母亲河。研究黄河水沙通量的变化规律对沿黄流域的环境治理、气候变 化和人民生活的影响,以及对优化黄河流域水资源分配、协调人地关系、调水调沙、防洪减灾 等方面都具有重要的理论指导意义。 附件 1 给出了位于小浪底水…...
【前端】CSS-Grid网格布局
目录 一、grid布局是什么二、grid布局的属性三、容器属性1、display①、语句②、属性值 2、grid-template-columns属性、grid-template-rows属性①、定义②、属性值1)、固定的列宽和行高2)、repeat()函数3)、auto-fill关键字4)、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 求组合数(二)
题目链接:求组合数 II #include <iostream> #include <algorithm>using namespace std;typedef long long LL; const int mod 1e9 7; const int N 100010;// 阶乘,阶乘的逆 int fact[N], infact[N];LL qmi(int a, int k, int p) {int res…...
k8s service的一些特性
文章目录 Service分发负载的策略同一端口通过不同协议暴露Headless Service的负载分发策略 Service分发负载的策略 大家都知道,一个service可以对应多个pod,那么一定要有一些方法来把service接收到的请求(负载)转发到pod上。 一般…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
