何でこれが詰まっちゃうかな・・・。
問題概要
原文 → D: 権力 - 京都大学プログラミングコンテスト2012 | AtCoder
個の区間がある。 を被覆するには、区間はいくつ必要であるか、その最小値を答えよ。
解説
まず、地点 を被覆する区間があるかを調べます。もし存在するならば、その中で一番右まで被覆できるものを選びます。存在しなければ Impossible
です。
次に、先ほど選んだ区間の右端 の地点を被覆する区間があるかを調べ、存在するならば一番右まで被覆できるものを選びます。
これを繰り返す貪欲法によって正答が得られ、計算量は です。
ソースコード
signed main() { int n, m; cin >> n >> m; int a[110], b[110]; rep(i,0,m) { cin >> a[i] >> b[i]; a[i]--; b[i]--; } bool covered[110] = {}; int ans = 0; rep(i,0,n) { if(covered[i]) continue; int r = -1; rep(j,0,m) { if(a[j] <= i && i <= b[j]) { r = max(r, b[j]); } } if(r == -1) { cout << "Impossible" << endl; return 0; } repq(j,i,r) covered[j] = true; ans++; } cout << ans << endl; return 0; }
どうも区間の問題が苦手らしい。