| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 线段覆盖 | ★☆☆☆☆ | 答案正确 | 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;
}
|
CloudLunar