题目描述
原题来自：Southwestern Europe 2002，题面可参考 POJ 1201。
给定
n
n 个闭区间
[a_i,b_i]
[ai
,bi
] 和
n
n 个整数
c_i
ci
。你需要构造一个整数集合
Z
Z，使得对于任意
i\in [1,n]
i∈[1,n]，
Z
Z 中满足
a_i\le x\le b_i
ai
≤x≤bi
的整数
x
x 不少于
c_i
c
i
个，求这样的整数集合
Z
Z 最少包含多少个数。
简而言之就是，从
0\sim 5\times 10^4
0∼5×104 中选出尽量少的整数，使每个区间
[a_i,b_i]
[a
i
,bi
] 内都有至少
c_i
ci
个数被选出。
输入
第一行一个整数
n
n，表示区间个数；
以下
n
n 行每行描述这些区间，第
i+1
i+1 行三个整数
a_i,b_i,c_i
ai
,bi
,ci
，由空格隔开。
输出
一行，输出满足要求的序列最少整数个数。
样例输入
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
样例输出
6
提示
数据范围与提示
对于全部数据，
1\le n\le 5\times 10^4,0\le a_i\le b_i\le 5\times 10^4,1\le c_i\le b_i-a_i+1
1≤n≤5×104,0≤ai
≤bi
≤5×104,1≤ci
≤bi
−ai
+1。
来源/分类
ybttg 差分约束系统