传送门

描述

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.

输入

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.

输出

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.

样例

• Input
  5
  3 7 3
  8 10 3
  6 8 1
  1 3 1
  10 11 1
• Output
  6

思路

• 题意：找一个区间z的大小，满足给定n组abc中,z在[a,b]中至少c个数，求最小的区间大小
• 求最小值，找最长路
• 用i表示0~i中在z的数，对于相邻的两个数i和i+1，满足：i+1 - i<=1 , i+1 - i >=0,故建边i+1 i -1，i i+1 0
• 对于给定的a,b,c：因为是闭区间，所以满足b+1 - a >=c,故建边 a b+1 c
• spfa 链式向前星

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

#include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define LL long long #define INIT(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=5e4+7; struct Node{
         int To,Dis,Next;}; Node Edge[500005];int top=0; int Begin[maxn],used[maxn],dis[maxn],n=-1,m; void add(int x,int y,int w){
            Edge[top]=(Node){y,w,Begin[x]};     Begin[x]=top++; } int spfa(int t){
            INIT(used,0);INIT(dis,-1);     dis[t]=0;     queue
              
               road; road.push(t);used[t]=1; while(!road.empty()){ int now=road.front();used[now]=0;road.pop(); for(int i=Begin[now];i!=-1;i=Edge[i].Next){ int ne=Edge[i].To; if(dis[ne]