poj 1716 Integer Intervals (差分约束或贪心)

Integer Intervals

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 12192		Accepted: 5145

Description

An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

Input

The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output

Output the minimal number of elements in a set containing at least two different integers from each interval.

Sample Input

Sample Output

Source

CEOI 1997

参考: http://blog.csdn.net/lyy289065406/article/details/6648679

贪心算法的思想我没证明，是参考别人的，不过不知道代码为什么没有过..所以就不贴出来了

差分约束的算法我自己也想了一下，其实并不难，不知道为什么老是错..可能poj的数据比较大吧

所以代码我也是参考别人的，自己的改了一段时间还没改好就没改了，贴一下：

 1 //Accepted    324K    297MS    C++    1088B    2013-12-01 22:11:55
 2 /*
 3 
 4     题意:
 5         给出n个区间[ai,bi]，求在每个区间内最少有两个数的一组数
 6         
 7     差分约束：
 8         S[ai - 1] <= S[bi] - 2 
 9         S[i] <= S[i - 1] + 1 
10         S[i - 1] <= S[i] 
11         
12     自己看着建吧.. 
13  
14 */
15 #include<iostream>
16 #include<queue>
17 #include<string.h>
18 #define N 10005
19 #define inf 0x7ffffff
20 using namespace std;
21 struct node{
22     int s,e;
23 }edge[N];
24 int d[N];
25 int n,up,down;
26 void bellman_ford()
27 {
28     memset(d,0,sizeof(d));
29     int flag=1;
30     while(flag){
31         flag=0;
32         for(int i=0;i<n;i++)
33             if(d[edge[i].s]>d[edge[i].e]-2){
34                 d[edge[i].s]=d[edge[i].e]-2;
35                 flag=1; 
36             }
37         for(int i=down;i<up;i++)
38             if(d[i+1]>d[i]+1){
39                 d[i+1]=d[i]+1;
40                 flag=1;
41             }
42         for(int i=up-1;i>=down;i--)
43             if(d[i]>d[i+1]){
44                 d[i]=d[i+1];
45                 flag=1;
46             }
47     }
48 }
49 int main(void)
50 {
51     while(cin>>n)
52     {
53         up=0;
54         down=n;
55         for(int i=0;i<n;i++){
56             int a,b;
57             cin>>a>>b;
58             edge[i].s=a;
59             edge[i].e=b+1;
60             if(down>a) down=a;
61             if(up<b+1) up=b+1;
62         }
63         bellman_ford();
64         cout<<d[up]-d[down]<<endl;
65     }
66     return 0;
67 }

poj 1716 Integer Intervals (差分约束 或 贪心)

poj 1716 Integer Intervals (差分约束或贪心)