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

蓝桥杯 17110抓娃娃

问题描述

小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上,第 i 条线段的左端点在 li,右端点在 ri​。小明用 m 个区间去框这些线段,第 i个区间的范围是 [Li​, Ri​]。如果一个线段有 至少一半 的长度被包含在某个区间内,则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?

输入格式

输入共 n+m+1 行。

第一行为两个正整数 n, m。

后面 n 行,每行两个整数 li​, ri​。

后面 m 行,每行两个整数Li​, Ri​。

输出格式

输出共 m 行,每行一个整数。

样例输入

3 2
1 2
1 3
3 4
1 4
2 4

样例输出

3
2

评测用例规模与约定

对于 20%20% 的数据,保证 n,m≤10^{3}

对于 100%100% 的数据,保证 n,m≤10^{5},li​<ri​,0<li,ri,Li,Ri≤10^{6},max⁡{ri−li}≤min⁡{Ri−Li}.

运行限制

语言最大运行时间最大运行内存
C++1s256M
C1s256M
Java3s256M
Python33s256M
PyPy33s256M
Go3s256M
JavaScript3s256M

 

首先题目保证了 max{ri​−li​}≤min{Ri​−Li​},那么如果某个区间包含了某个线段,则该区间一定包含了这个线段的中点。

我们就可以在输入 li​,ri​ 的时候,标记其中点 (mp[(l+r)/2]++),再做一遍前缀和,最后查询时 [Li​,Ri​] 这个区间的和就是答案。

注意:

有可能会出现中点的位置是个小数这种情况,所以我们不妨把所有坐标都 ×2 (不要忘记数组大小也要开两倍),以避免上述情况的发生。

 

#include<iostream>
using namespace std;

const int N = 2e6+10;
int n, m;  //n条线段  m个区间
int mp[N];

int main()
{
	cin>>n>>m;
	int l, r;
	for(int i=1; i<=n; ++i)
	{
		cin>>l>>r;
		mp[l+r]++;  //记录每条线段中点的位置 
	}
	
	for(int i=1; i<N; ++i)
	{
		mp[i] += mp[i-1];
	}
	
	for(int i=1; i<=m; ++i)
	{
		cin>>l>>r;
		l *= 2;
		r *= 2;
		
		//一段区间包含了多少个中点就覆盖了多少条线段 
		cout<<mp[r] - mp[l-1]<<endl;  //l-1:线段的中点恰好在 L 上 
	}
	
	return 0;
}

 


http://www.kler.cn/a/587196.html

相关文章:

  • 【SpringMVC】常用注解:@CookieValue
  • synchronized与 Java内置锁(未写完)
  • 《TCP/IP网络编程》学习笔记 | Chapter 18:多线程服务器端的实现
  • 《Electron 学习之旅:从入门到实践》
  • RK3588 openssl-3.4.1 编译安装
  • unity生命周期
  • vue埋点
  • Python实现NOA星雀优化算法优化随机森林分类模型项目实战
  • 前端工程化之前端工程化详解 包管理工具
  • Haskell语言的二进制与编码
  • 基于隐私计算的数据共享与分析平台V1.0源代码说明文档
  • AtCoder AT_abc397_d [ABC397D] Cubes
  • leetcode hot100普通动态规划/基础DP
  • OpenHarmony-SELinux配置
  • R语言高效数据处理-自定义格式EXCEL数据输出
  • 洞悉C++内存结构:解锁深层优化潜力
  • redis主从搭建
  • 《鸿蒙系统下AI模型训练加速:时间成本的深度剖析与优化策略》
  • 【ElasticSearch】学习笔记
  • 如何让ai问答机器人通人性?