首页 > 代码库 > poj 1716 Integer Intervals
poj 1716 Integer Intervals
题目:
在数轴上有n个区间,每个区间都是连续的整数区间。现在要在数轴上任取一堆元素,构成一个集合V,要求每个区间和V的交集至少有两个不同的元素。求V的最小的元素个数。
问题分析:
可以使用贪心算法,最终结果肯定是小于大于2×n的,如果两个集合之间有相同的元素,那么选相同的元素必然会使结果更小,当我们以e排序后,如果有相同的必然是最后的元素。所以贪心的策略就是如果一个区间最后两个元素没被选就选上。
步骤:
先对所有区间按末端点排序。
取第i个区间的最后两个元素Selem和Eelem。
若第i+1个区间包含了这两个元素,则跳到下一个区间所取的元素个数+0
若第i+1个区间只包含了这两个元素中的一个(由于有序,所以必定是包含Eelem),则取第i+1个区间的最后一个元素,所取的元素个数+1。为了方便下一区间的比较,更新Selem和Eelem的值,使他们为当前V集合中最后的两个元素。
若第i+1个区间没有包含这两个元素,则第i+1个区间的最后两个元素,所取的元素个数+2。为了方便下一区间的比较,更新Selem和Eelem的值,使他们为当前V集合中最后的两个元素。
Selem初始化为第一个区间的最后倒数第2个元素,
Eelem初始化为第一个区间的最后的元素,
所取的元素个数初始化为2 (就是Selem和Eelem)。
#include <stdio.h> #include <algorithm> using namespace std; const int M = 10005; struct interval { int s, e; }inter[M]; bool cmp(interval x, interval y) { return x.e < y.e; } int main() { int n; while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) { scanf("%d %d", &inter[i].s, &inter[i].e); } sort(inter, inter+n, cmp); int Selem = inter[0].e-1, Eelem = inter[0].e; //取当前区间的两个元素,初始化为最后面两个 int ans = 2; //至少取sum个元素才能保证每个区间至少含有其中的2个元素 for (int i = 1; i < n; i++) { if (Selem >= inter[i].s) //前一个区间所取的两个元素都在当前区间内 continue; else if (Eelem >= inter[i].s) //前一个区间所取的只有一个元素在当前区间内 { Selem = Eelem; Eelem = inter[i].e; //按序更新当前区间所取的两个元素:Selem与Eelem ans += 1; //Eelem是新取的一个元素 } else //前一个区间所取的没有一个元素在当前区间内 { Selem = inter[i].e-1; Eelem = inter[i].e; //按序更新当前区间所取的两个元素:Selem与Eelem ans += 2; //Selem与Eelem是新取的两个元素 } } printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。