# Initiate

posts - 14, comments - 3, trackbacks - 0, articles - 0
C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Intervals

 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 8965 Accepted: 3318

Description

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.

Input

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

Sample Input

5

3 7 3

8 10 3

6 8 1

1 3 1

10 11 1

Sample Output

6

1>=s[i+1]-s[i]>=0

Source Code

1 #include<iostream>
2 #include<vector>//for map
3 #include<queue>//for spfa
4 using namespace std;
5 #define MAXN 50010
6 #define pb push_back
7 int dis[MAXN],used[MAXN];
8 int aa=INT_MAX,bb=-1;//aa最小bb最大
9 struct edge
10 {
11     int p;
12     int len;
13 }tmp;
14 vector<edge>map[MAXN];
15
16 void spfa()
17 {
18     int i,t;
19     queue<int>Q;
20     for(i=aa;i<=bb;i++)
21         dis[i]=-INT_MAX;
22     dis[aa]=0;
23     used[aa]=1;//先进一个
24     Q.push(aa);
25     while(!Q.empty())
26     {
27         t=Q.front();
28         Q.pop();
29         used[t]=0;//出队列过后,还可能再进
30         int nt=map[t].size();
31         for(i=0;i<nt;i++)
32         {
33             if(dis[map[t][i].p]<dis[t]+map[t][i].len)//求最长路
34             {
35                 dis[map[t][i].p]=dis[t]+map[t][i].len;
36                  if(!used[map[t][i].p])
37                  {
38                       used[map[t][i].p]=1;
39                       Q.push(map[t][i].p);
40                  }
41             }
42            }
43     }
44 }
45 int main()
46 {
47     int i,n;
48     scanf("%d",&n);
49     int u,v,w;
50     for(i=1;i<=n;i++)
51     {
52         scanf("%d%d%d",&u,&v,&w);
53         if(u<aa) aa=u;
54         if(v+1>bb) bb=v+1;
55         tmp.len=w;
56         tmp.p=v+1;
57         map[u].pb(tmp);
58     }//添加ci边
59     for(i=aa;i<=bb;i++)
60     {
61         tmp.len=0;
62         tmp.p=i+1;
63         map[i].pb(tmp);
64         tmp.len=-1;
65         tmp.p=i;
66         map[i+1].pb(tmp);
67     }//添加0边和-1边
68     spfa();
69     printf("%d\n",dis[bb]);
70     return 0;
71 }
72