UVA 10020 Minimal coverage ( 水題區間覆蓋 )
UVa Online Judge
很單純的區間覆蓋問題。注意覆蓋的是端點而非區間。
#include <bits/stdc++.h> using namespace std; const int MAXLR = 5e4 + 4; const int MAXM = 5000 + 3; const int MAXP = 1e6 + 5; int m; typedef pair<int, int> pii; int n; pii p[MAXP]; void solve(){ sort( p, p + n ); n = unique( p, p + n ) - p; int best_idx, pos = 0, cnt = 0; vector<int> chosen; int rb = 0; while( pos < m ){ best_idx = -1; while( rb < n && p[ rb ].first <= pos ){ if( best_idx < 0 || p[ rb ].second > p[ best_idx ].second ) best_idx = rb; ++rb; } if( best_idx < 0 ) break; ++cnt; pos = p[ best_idx ].second; chosen.push_back( best_idx ); } if( pos < m ){ puts("0"); return; } printf("%d\n", cnt); assert( cnt == chosen.size() ); for(int i = 0; i < cnt; ++i) printf("%d %d\n", p[ chosen[ i ] ].first, p[ chosen[ i ] ].second); } int main(){ int T; scanf("%d", &T); while( T-- ){ scanf("%d", &m); n = 0; while( true ){ int a, b; scanf("%d%d", &a, &b); if( a == 0 && b == 0 ) break; p[ n++ ] = pii( a, b ); } solve(); if( T ) puts(""); } return 0; }