Intervals

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 22781		Accepted: 8613

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

53 7 38 10 36 8 11 3 110 11 1

Sample Output

6

Source

 

题目大意：有n个区间，每个区间有3个值，ai，bi，ci代表，在区间[ai,bi]上至少要选择ci个整数点，ci可以在区间内任意取不重复的点

现在要满足所有区间的自身条件，问最少选多少个点

解题思路：

差分约束的思想：可以肯定的是s[bi]-s[ai-1]>=ci; 为什么要ai-1，是因为ai也要选进来

在一个是s[i]-s[i-1]<=1;

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

所以整理上面三个式子可以得到约束条件：

①s[ai-1]-s[bi] <= -ci

②s[i]-s[i-1] <= 1

③s[i-1]-s[i] <= 0

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;int n,minn,maxx,cnt;bool vis[50010];int dist[50010];struct node{ int to,len,next;}e[210000];int head[50010];void add(int u,int v,int len){ e[++cnt].to=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt;}void spfa(){ queue
               
                 q; for(int i=minn;i<=maxx;i++) { vis[i]=0; dist[i]=INT_MAX; } dist[maxx]=0; vis[maxx]=1; q.push(maxx); while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=head[x];i;i=e[i].next) { int v=e[i].to; int w=e[i].len; if(dist[v]>dist[x]+w) { dist[v]=dist[x]+w; if(!vis[v]) { q.push(v); vis[v]=1; } } } }}int main(){ scanf("%d",&n); cnt=1; minn=INT_MAX,maxx=-INT_MAX; for(int i=1;i<=n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); minn=min(a,minn); maxx=max(maxx,b+1); add(b+1,a,-c); } for(int i=minn;i