题目传送门: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; }
Comments NOTHING