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

    ACM-POJ EXP 108阅读 0评论

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


    大致题意

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

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

    要求每个区间[ai,bi]和元素集合V的交集至少有ci不同的元素

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

    解题思路

    POJ1716 的升级版,只是边权不是固定,而是变化的而已

    其实只要把 POJ1716 的 范围 和“固定边权2”改为ci 就能直接AC了

    注意本题只能用差分约束+Relax解决,不能像 POJ1716 那样用贪心。


    建议先去把我做 POJ1716 的方法看懂了,再来做这题,不过我还是重述一下思路

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

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

    因此有

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

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

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

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

    故建图,使图中每一组边,均满足(注意三条式子的不等号方向要一致,这个很重要):
      S[ai – 1] <= S[bi] – ci
      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] – ci ;

    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中的一个元素;最小顶点到最大顶点其实就是所有输入的区间中,最小的左端点到最大的右端点这个范围)。

    注意,经过我测试,像POJ1716一样,本题变量的定义均要从全局定义,否则WA,什么原因我也不清楚(变量和数组的大小都只有50000,真是神了)

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

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

    表情

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

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