• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1716 – Integer Intervals

    ACM-POJ EXP 171阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    给出数轴上的n个区间,每个区间都是连续的int区间。

    现在要在数轴上任意取一堆元素,构成一个元素集合V

    要求每个区间和元素集合V的交集至少有两个不同的元素

    求集合V最小的元素个数。

    解题思路

    本题有两种解法: 贪心算法 或 差分约束


    一、贪心算法

    先对所有区间按末端点排序

    取第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)


    二、差分约束+Relax

    设s[x] = 从0到x 的所有在集合中的数的个数

    则ai到bi的个数即S[bi] – S[ai-1]。

    因此有

    (1) S[bi] – S[ai-1] >= 2。

    又根据s[x]本身的性质,后面的一定不比前面的小,后面的最多比前面多一,有:

    (2) s[i + 1] – s[i] >= 0

    (3) s[i + 1] – s[i] <= 1

    故建图,使图中每一组边,均满足(注意三条式子的不等号方向要一致,这个很重要):
      S[ai – 1] <= S[bi] – 2
      S[i] <= S[i – 1] + 1
      S[i – 1] <= S[i]

    上面三式,可把s[x]看作源点(假设存在)到各点的最短距离,初始化为0;

    常数为边(ai – 1,bi)的边权

    当存在不满足这三条式子的边时,对这条边进行Relax操作,更新不等号左边的变量

    其实就是Bellman-Ford算法的核心部分

    if( S[ai – 1] > S[bi] – 2 ) S[ai – 1] = S[bi] – 2;

    if( S[i] > S[i – 1] + 1 ) S[i] > S[i – 1] + 1;

    if( S[i – 1] > S[i] ) S[i – 1] = S[i];

    最后源点到最大顶点的距离减去源点到最小顶点的距离就是所求(其实一个单位距离就代表V中的一个元素;最小顶点到最大顶点其实就是所有输入的区间中,最小的左端点到最大的右端点这个范围)。

    注意,经过我测试,本题变量的定义均要从全局定义,否则WA,什么原因我也不清楚(变量和数组的大小都只有10000,真是神了),只能说POJ太虐人了,白白耗了我一堆时间。


    方法一: 贪心算法

    转载请注明:EXP 技术分享博客 » POJ1716 – Integer Intervals

    喜欢 (1) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址