ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[牛客小白月赛54]C.School(区间合并 + 二分)

2022年8月14日 175点热度 1人点赞 0条评论

题目传送门:C-School_牛客小白月赛54 (nowcoder.com)

思路 / Thought

一般遇到时间的题,都会将单位统一化,比如统一成“分钟”,那么这么的a时b分,就相当于是第a * m + b分钟。问题就转化成了给定一个1e13规模的区域,有1e3个区间,然后给定一个点问是否在这些区间覆盖的地方。

先读入区间,根据左端点排序,然后将区间合并成互不相交的若干个区间。

最后判断x点是否被覆盖了,只需要找到最后一个小于等于x的左端点(第一个大于x的左端点的前一个),判断右端点是否大于等于x即可。

代码 / Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

void solve()
{
	int n, h, m, q;cin >> n >> h >> m >> q;
	vector<pair<int, int> > v, t;//t是合并后的区间数组
	for(int i = 1;i <= n; ++ i)
	{
		int a, b, c, d;cin >> a >> b >> c >> d;
		a = a * m + b, c = c * m + d;
		v.push_back({a, c});
	}
	sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b){return a.fi < b.fi;});
	t.push_back(v[0]);
	for(auto &i : v)
	{
		if(i.fi <= t.back().se)t.back().se = max(t.back().se, i.se);
		else t.push_back(i);
	}
	while(q --)
	{
		int x, y;cin >> x >> y;
		x = x * m + y;
		int pos = upper_bound(t.begin(), t.end(), x, [](const int &a, const pair<int, int> &b){return a < b.fi;}) - t.begin() - 1;
		if(pos < t.size() && t[pos].fi <= x && x <= t[pos].se)cout << "No" << '\n';
		else cout << "Yes" << '\n';
	}
}


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 二分 区间 牛客网 算法竞赛
最后更新:2022年8月14日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号