传送门
描述
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.
样例
- Input53 7 38 10 36 8 11 3 110 11 1
- Output6
思路
- 题意:找一个区间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 |