CodeVS/1214

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
线段覆盖	★☆☆☆☆	答案正确	100	2014-10-11 12:53:32	无

题意

在数轴上，有若干区间，要求去掉若干区间后，使得没有一个点同时属于两个以上区间内部（端点可以重叠），如图。

题解

采取贪心的策略。

什么样的区间被选择风险最小，当然是结束点最小的区间：

于是按照这个策略，就优先选择能够放下去的结束点最小的区间，于是排序+判断一下就可以了。

代码

1214.cpp代码已折叠 展开折叠内容

显示/移除行号 #include<iostream> #include<algorithm> #include<climits> std::pair<int,int> p[101]; int n; void init() { std::cin>>n; for(int i=1;i<=n;++i) { std::cin>>p[i].first>>p[i].second; if(p[i].first<p[i].second) std::swap(p[i].first,p[i].second); } std::sort(p+1,p+n+1); } const int process() { int last=INT_MIN,count=0; for(int i=1;i<=n;++i) { if(last<=p[i].second) { last=p[i].first; ++count; } } return count; } int main() { init(); std::cout<<process(); return 0; }