(以“分类:贪心 ==摘要== {{信息题|线段覆盖|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_01.png}}
 
==题解==
 
==题解==
 
采取贪心的策略。
 
采取贪心的策略。
  
 
什么样的区间被选择风险最小,当然是结束点最小的区间:
 
什么样的区间被选择风险最小,当然是结束点最小的区间:
{{大照片| |Knowledge/Algorithm/CodeVS/1214_02.png}}
+
{{无边框大照片|Knowledge/Algorithm/CodeVS/1214_02.png}}
 
于是按照这个策略,就优先选择能够放下去的结束点最小的区间,于是排序+判断一下就可以了。
 
于是按照这个策略,就优先选择能够放下去的结束点最小的区间,于是排序+判断一下就可以了。
 
==代码==
 
==代码==

2014年10月11日 (六) 13:11的最后版本

摘要

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

题意

在数轴上,有若干区间,要求去掉若干区间后,使得没有一个点同时属于两个以上区间内部(端点可以重叠),如图。 1214_01.png

题解

采取贪心的策略。

什么样的区间被选择风险最小,当然是结束点最小的区间: 1214_02.png

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

代码

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;
}

著作权声明[编辑]

关于[编辑]