（以“分类:贪心 ==摘要== {{信息题|线段覆盖|http://www.codevs.cn/problem/1214/|1|100|time=2014-10-11 12:53:32}} ==题意== 在数轴上，有若干区间...”为内容创建页面） |
小 （修改模板为无边框大照片） |
||
| 第4行： | 第4行： | ||
==题意== | ==题意== | ||
在数轴上，有若干区间，要求去掉若干区间后，使得没有一个点同时属于两个以上区间内部（端点可以重叠），如图。 | 在数轴上，有若干区间，要求去掉若干区间后，使得没有一个点同时属于两个以上区间内部（端点可以重叠），如图。 | ||
| − | {{ | + | {{无边框大照片|Knowledge/Algorithm/CodeVS/1214_01.png}} |
==题解== | ==题解== | ||
采取贪心的策略。 | 采取贪心的策略。 | ||
什么样的区间被选择风险最小，当然是结束点最小的区间： | 什么样的区间被选择风险最小，当然是结束点最小的区间： | ||
| − | {{ | + | {{无边框大照片|Knowledge/Algorithm/CodeVS/1214_02.png}} |
于是按照这个策略，就优先选择能够放下去的结束点最小的区间，于是排序+判断一下就可以了。 | 于是按照这个策略，就优先选择能够放下去的结束点最小的区间，于是排序+判断一下就可以了。 | ||
==代码== | ==代码== | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 线段覆盖 | ★☆☆☆☆ | 答案正确 | 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