Destroyer Takahashi
問題
D – Destroyer Takahashi
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…
記録
- 2022/6/28 OK
- 2022/3/4 解法わからず。
解法
- 区間スケジューリング問題。
R
でソート(昇順)する。- 小さい
R
から叩く。\(R + D – 1\) までに別のR
があれば一緒に消える。
コード例
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using P = pair<int, int>; #define rep(i, n) for(int i = 0; i < (n); ++i) // using mint = modint998244353; // using mint = modint1000000007; // const int mod = 1000000007; // const ll INF = 1LL << 60; // const int INF = 1001001001; int main() { int N, D; cin >> N >> D; vector<P> wall(N); rep(i, N) { int L, R; cin >> L >> R; wall[i] = make_pair(R, L); } sort(wall.begin(), wall.end()); int ans = 0; int last = 0; rep(i, N) { if(i == 0) { last = wall[i].first; ans++; continue; } if(last + D - 1 < wall[i].second) { last = wall[i].first; ans++; } } cout << ans << endl; return 0; }