Logo CloudLunar

“CodeVS/1214”的版本间的差异

（以“分类:贪心 ==摘要== {{信息题|线段覆盖|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代码已折叠
展开折叠内容
显示/移除行号
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<climits>
  4. std::pair<int,int> p[101];
  5. int n;
  6. void init()
  7. {
  8.     std::cin>>n;
  9.     for(int i=1;i<=n;++i)
  10.     {
  11.         std::cin>>p[i].first>>p[i].second;
  12.         if(p[i].first<p[i].second)
  13.             std::swap(p[i].first,p[i].second);
  14.     }
  15.     std::sort(p+1,p+n+1);
  16. }
  17. const int process()
  18. {
  19.     int last=INT_MIN,count=0;
  20.     for(int i=1;i<=n;++i)
  21.     {
  22.         if(last<=p[i].second)
  23.         {
  24.             last=p[i].first;
  25.             ++count;
  26.         }
  27.     }
  28.     return count;
  29. }
  30. int main()
  31. {
  32.     init();
  33.     std::cout<<process();
  34.     return 0;
  35. }
取自“https://blog.CloudLunar.com/index.php?title=CodeVS/1214&oldid=577”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]