1752 【差分约束】 integer intervals(整数区间)

《1752 【差分约束】 integer intervals(整数区间)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【差分约束】IntegerIntervals（整数区间）TimeLimit:1000MS MemoryLimit:65536KTotalSubmit:7Accepted:3Description整数区间（intervals.pas/c/cpp）【问题描述】一个整数区间[a，b]，a写一个程序是：求一个点集，使得每个区间都至少有2个整数在这个点集里面，问这个点集最少有几个点。Input第一行包含区间总数n，1<=n<=10000。接下来n行，每行包含两个整数a、b，用一个空格隔开，0<=a

2、输出一个整数，表示包含每个区间至少有两个不同整数的点集的最少点数量。SampleInput436240247SampleOutput4SourceCEOI1997大致题意：给出数轴上的n个区间，每个区间都是连续的int区间。现在要在数轴上任意取一堆元素，构成一个元素集合V要求每个区间和元素集合V的交集至少有两个不同的元素求集合V最小的元素个数。 解题思路：一、贪心算法先对所有区间按末端点排序取第i个区间的最后两个元素Selem和Eelem若第i+1个区间包含了这两个元素，则跳到下一个区间所取的元素个数+0[(**)]若第i+1个区间只

3、包含了这两个元素中的一个（由于有序，所以必定是包含Eelem），则取第i+1个区间的最后一个元素，所取的元素个数+1。为了方便下一区间的比较，更新Selem和Eelem的值，使他们为当前V集合中最后的两个元素。(*[*)]若第i+1个区间没有包含这两个元素，则第i+1个区间的最后两个元素，所取的元素个数+2。为了方便下一区间的比较，更新Selem和Eelem的值，使他们为当前V集合中最后的两个元素。(**)[] Selem初始化为第一个区间的最后倒数第2个元素Eelem初始化为第一个区间的最后的元素所取的元素个数初始化为2(就是Sel

4、em和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]-2S[i]<=S[i-1]+1S[i-1]<=S[i]上面三式，可把s[x]看作源点（假设存在）到各点

5、的最短距离，初始化为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中的一个元素；最小顶点到最大顶点其实就是所有输入的区间中，最小的左端点到最大

6、的右端点这个范围）。·Const{贪心}·maxn=10000;·varn,ans:integer;·a:array[1..maxn,1..2]ofinteger;··procedureqsort(l,r:integer);·vari,j,mid,mid2:integer;·t:array[1..2]ofinteger;·begin·ifl

7、=mid)and(a[i,1]>mid2))doinc(i);·while(a[j,2]>mid)or((a[j,2]=mid)and(a[j,1]=j;·qsort(l,j);·qsort(i,r);·end;·end;··proceduremain;·var·i,j,k:integer;·begin·readln(n);·fori:=1tondoreadln

8、(a[i,1],a[i,2]);·qsort(1,n);·ans:=2;·i:=a[1,2]-1;j:=a[1,2];·fork:=2tondo·if(i>=a[k,1])and(j>=a[k,1])thencontin