蓝桥杯刷题 前缀和与差分-[NewOJ P1819]推箱子(C++)

题目描述

在一个高度为H的箱子前方,有一个长和高为N的障碍物。
障碍物的每一列存在一个连续的缺口,第i列的缺口从第l各单位到第h个单位(从底部由0开始数)。
现在请你清理出一条高度为H的通道,使得箱子可以直接推出去。
请输出最少需要清理的障碍物面积。
如下图为样例中的障碍物,长和高度均为5,箱子高度为2。(不需要考虑箱子会掉入某些坑中)
 



最少需要移除两个单位的障碍物可以造出一条高度为2的通道。

输入格式

输入第一行为两个正整数N和H,表示障碍物的尺寸和箱子的高度,1≤H≤N≤1000000。
接下来N行,每行包含两个整数li和hi,表示第i列缺口的范围,0≤li≤hi<N。

输出格式

输出一个数字表示答案。

输入样例

5 2
2 3
1 2
2 3
1 2
2 3

输出样例

2

知识点:前缀和与差分 

 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll a[N];
ll sum=LLONG_MAX;
void insert(ll l,ll r,ll c)
{
  a[l]+=c;
  a[r+1]-=c;
}
int main() {
	ll n,h,li,hi;
	cin>>n>>h;
	for(int i=1;i<=n;i++)
	{
		cin>>li>>hi;
		insert(li,hi,1);
	}
	for(int i=1;i<=n;i++)
	{
		a[i]+=a[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=n-a[i];//每一行剩余的障碍物数量 
	}
	for(int i=1;i<=n;i++)
	{
		a[i]+=a[i-1];
	}
	for(int i=1;i<=n-h+1;i++)
	{
		sum=min(sum,(a[i+h-1]-a[i-1]));
	}
	cout<<sum<<endl; 
	return 0;
}

题目链接:http://oj.ecustacm.cn/problem.php?id=1819

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/522004.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

蓝桥杯刷题-09-三国游戏-贪心⭐⭐⭐

蓝桥杯2023年第十四届省赛真题-三国游戏 小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件&#xff0c;每个事件之间相互独立且最多只会发生一次&#xff0c;当第 i 个事件发生时会分别让 X, Y,…

GitHub突破1000星!上交、清华开源个性化联邦学习算法库PFLlib

©PaperWeekly 原创 作者 | 张剑清 单位 | 上海交通大学、清华大学&#xff08;AIR&#xff09; 研究方向 | 联邦学习 我们在 GitHub 上开源了一个个性化联邦学习算法仓库&#xff08;PFLlib&#xff09;&#xff0c;目前已经获得 1K 个 Star 和 200 个 Fork&#xff0c;在…

【C++】探索C++中的类与对象(下)---深入理解C++中的关键概念与应用

​​ &#x1f331;博客主页&#xff1a;青竹雾色间. &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 ✨人生如寄&#xff0c;多忧何为 ✨ 在C编程中&#xff0c;有许多重要的概念和特性&#xff0c;包括构造函数、explicit关键字、静态成员、友元以及内部类…

58 vue-cli 以及 webpack 提供的默认的插件, 配置

前言 vue-cli 这边作为驱动 webpack 的一个应用 它需要构造 webpack 所需要的上下文, 以及参数 这里 我们来关注一下 vue-cli 这边为 webpack 构造的参数 的相关处理 webpack 这边上下文的配置, 主要分为了几个部分, Entry, Output, Module, Resolve, Plugin, DevServer, O…

Linux下Qt生成程序崩溃文件

文章目录 1.背景2.Qt编译生成程序2.1.profile模式的本质 3.执行程序&#xff0c;得到core文件4.代码定位4.1.直接使用gdb4.2.使用QtCreator 5.总结6.题外话6.1.profile模式和debug模式的区别 1.背景 在使用Qt时&#xff0c;假如在windows&#xff0c;当软件崩溃时&#xff0c;…

太阳能光伏电子实验酸洗用PFA方槽耐受强酸碱耐高温

PFA清洗槽是四氟清洗桶后的升级款&#xff0c;主要用于半导体光伏光电等行业&#xff0c;一体成型&#xff0c;无需担心漏液&#xff0c;表面光滑无毛刺。 别名PFA浸泡桶、PFA酸缸、PFA方槽等&#xff0c;可定制尺寸&#xff0c;可配套盖子&#xff0c;盖子有PFA/PTFE两种材质…

uniapp:聊天消息列表(好友列表+私人单聊)支持App、H5、小程序

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 &#x1f4dd; 个人网站 :《 江城开朗的豌豆&#x1fadb; 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 ⭐ 文章简介&#xff08;效果图展示&#xff…

【SQL】1890. 2020年最后一次登录(简单写法;窗口函数写法)

前述 sql 中 between 的边界问题 ---- between 边界&#xff1a;闭区间&#xff0c;not between 边界&#xff1a;开区间 在 sql 中&#xff0c; between 边界&#xff1a;闭区间not between 边界&#xff1a;开区间 题目描述 leetcode题目&#xff1a;1890. 2020年最后一…

LC 235.二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个结点 p、q&#xff0c;最近公共祖先表示为一个结点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&…

量身定制:选择能够解决企业问题的六西格玛培训机构

现在的培训机构太多了&#xff0c;都在打着六西格玛管理的旗号&#xff0c;甚至有很多培训机构连六西格玛管理都没有学习过&#xff0c;就敢号称自己是六西格玛管理专家。在这个鱼龙混杂的市场上&#xff0c;很多企业对于选择什么样的培训机构&#xff0c;以及如何选择一家靠谱…

【话题】如何看待那些速成并精通软件书籍的神器

大家好&#xff0c;我是全栈小5&#xff0c;欢迎阅读小5的系列文章&#xff0c;这是《话题》系列文章 目录 背景1. 神话与现实1.1 理论与实践之间的鸿沟1.2 一劳永逸的错觉 2. 速成书籍的优势与局限2.1 优势&#xff1a;2.2 局限&#xff1a; 3. 如何有效利用速成书籍3.1 量力而…

第十二天--二维数组的彻底解刨--地址

1.二维数组我们用父子的地址来称呼二维数组的地址 比如arr[3][4] 这里的arr是二维数组的首地址&#xff0c;也是父数组的首地址&#xff0c;也是子数组的首地址 arr1父数组的地址偏移1&#xff0c;实际上是偏移了4*416个字节 arr[0]是子数组的首地址&#xff0c;arr[0]1是子数…

Ubuntu22.04安装Anaconda

一、下载安装包 下载地址&#xff1a;https://www.anaconda.com/download#Downloads 参考&#xff1a;Ubuntu下安装Anaconda的步骤&#xff08;带图&#xff09; - 知乎 下载Linux 64-Bit (x86) installer 二、安装 在当前路径下&#xff0c;执行命令&#xff1a; bash Ana…

Nifi同步过程中报错create_time字段找不到_实际目标表和源表中没有这个字段---大数据之Nifi工作笔记0066

很奇怪的问题,在使用nifi的时候碰到的,这里是用NIFI,把数据从postgresql中同步到mysql中, 首先postgresql中的源表,中是没有create_time这个字段的,但是同步的过程中报错了. 报错的内容是说,目标表中有个create_time字段,这个字段是必填的,但是传过来的flowfile文件中,的数据没…

智过网:一建继续教育,操作指南与周期解析

随着社会的快速发展和技术的不断更新&#xff0c;建筑行业对从业人员的专业素质要求也在逐步提高。为了确保一级建造师的专业技能能够与时俱进&#xff0c;满足行业发展的需求&#xff0c;继续教育成为了必不可少的环节。本文将详细解析一建继续教育的操作流程及其周期安排&…

洛谷 1126.机器人搬重物

思路&#xff1a;BFS 这道BFS可谓是细节爆炸&#xff0c;对于编程能力和判断条件的能力的考察非常之大。 对于这道题&#xff0c;我们还需要额外考虑一些因素&#xff0c;那就是对于障碍物的考虑和机器人方位的考虑。 首先我们看第一个问题&#xff0c;就是对于障碍物的考虑…

基于单片机放大电路程控放大特性参数设计

**单片机设计介绍&#xff0c;基于单片机放大电路程控放大特性参数设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机放大电路程控放大特性参数设计是一个结合了单片机编程和放大电路技术的综合性项目。以下是对该设计项目的概…

Dapr(三) Dapr核心组件的使用一

结合前两期 Dapr(一) 基于云原生了解Dapr(Dapr(一) 基于云原生了解Dapr-CSDN博客) Dapr(二) 分布式应用运行时搭建及服务调用(Dapr(二) 分布式应用运行时搭建及服务调用-CSDN博客) 下篇推出dapr服务注册与发现&#xff0c;dapr组件绑定&#xff0c;dapr Actor功能。 目录 1.…

LVGL可视化设计-Gui Guider

&#xff08;提示&#xff1a;本篇编辑状态中&#xff0c;完成了70%左右&#xff0c;争取4-8前完成) 一、Gui Guider 概述 免费&#xff01;免费&#xff01;免费&#xff01;支持 LVGL v7、 v8.3很方便的&#xff1a;安装、使用 (另一种主流的visual studio模拟&#xff0c;省…

#pragma once的作用

使用visual studio新建头文件时&#xff0c;第一行会出现如下默认代码&#xff0c; #pragma once 它是一种编译器指令&#xff0c;通常用于确保头文件只被包含一次&#xff0c;以避免产生重复定义的问题。当编译器处理一个源文件时&#xff0c;遇到#pragma once指令时&#xf…