ErikTse Runtime

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

[牛客小白月赛12]A.华华听月月唱歌(贪心 + 双指针)

2022年8月20日 115点热度 0人点赞 0条评论

题目传送门:A-华华听月月唱歌_牛客小白月赛12 (nowcoder.com)

思路 / Thought

既然是区间题,看一眼数据范围,N到了1e9,所以肯定要用vector将区间左右端点存下来处理。

先将所有区间按照左端点排序,然后用双指针每次向右拓展最大距离,如果最后右端点能够到达N,说明可以拼凑成功。

r表示从1可以到达的最远连续右端。

代码 / Code

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

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, M;cin >> N >> M;
	
	vector<pair<int, int> > v, t;
	for(int i = 1;i <= M; ++ i)
	{
		int x, y;cin >> x >> y;
		v.push_back({x, y});
	}
	sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b){return a.fi < b.fi;});
	
	int r = 0, ans = 0;//r表示可以连续到达的最右位置 
	for(int i = 0;i < M && r < N;)
	{
		int j = i, tr = 0;
		while(j < M && v[j].fi <= r + 1)tr = max(tr, v[j ++].se);
		if(tr <= r)break;//说明无法连接起来
		r = tr, i = j, ans ++;
	}
	
	cout << (r < N ? -1 : ans) << '\n'; 
	
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 双指针 思维 牛客网 贪心
最后更新:2022年8月20日

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号