UVA 10020(Minimal coverage)贪心

xiaoxiao2021-02-28  13

题目链接:https://vjudge.net/problem/UVA-10020

题意:给出一个数M,再给出若干个小区间,问能否用这些小区间覆盖【0,M】,可以就输出最少的区间个数和对应区间,否则输出0.

#include<bits/stdc++.h> using namespace std; vector<pair<int,int> >v,ans; bool cmp(pair<int,int> p1,pair<int,int>p2) { return p1.second>p2.second; } int main() { int T; while(cin>>T) { while(T--) { v.clear(); ans.clear(); int n; cin>>n; int l,r; while(cin>>l>>r&&(l||r)) { if(!(r<=0||l>=n)) v.push_back(make_pair(l,r)); } sort(v.begin(),v.end(),cmp); int now=0; while(now<n) { bool flag=false; for(int i=0;i<v.size();i++) { if(v[i].first<=now&&v[i].second>now) { ans.push_back(v[i]); now=v[i].second; v.erase(v.begin()+i); flag=true; i--; } } if(!flag) break; } if(T) cout<<endl; if(now>=n) { cout<<ans.size()<<endl; for(int i=0;i<ans.size();i++) { cout<<ans[i].first<<' '<<ans[i].second<<endl; } } else { cout<<0<<endl; } } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2800064.html

最新回复(0)