| 题目名称 | 3066. [POJ 1201]区间 |
|---|---|
| 输入输出 | intervals.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2018-12-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：12， 通过率：16.67% | ||||
 ┭┮﹏┭┮ |
100 | 0.014 s | 4.22 MiB | C++ |
|
小金 |
100 | 0.536 s | 34.34 MiB | C++ |
|
┭┮﹏┭┮ |
10 | 0.002 s | 3.76 MiB | C++ |
|
┭┮﹏┭┮ |
10 | 4.807 s | 13.37 MiB | C++ |
|
┭┮﹏┭┮ |
10 | 4.849 s | 15.20 MiB | C++ |
 LGLJ |
10 | 18.000 s | 10.66 MiB | C++ |
|
┭┮﹏┭┮ |
10 | 18.000 s | 15.04 MiB | C++ |
|
┭┮﹏┭┮ |
10 | 18.000 s | 17.10 MiB | C++ |
|
┭┮﹏┭┮ |
0 | 6.797 s | 17.10 MiB | C++ |
|
┭┮﹏┭┮ |
0 | 18.200 s | 33.39 MiB | C++ |
| 关于 区间 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
┭┮﹏┭┮ 差分约束小记
┭┮﹏┭┮
2024-01-12 21:17
2楼
| ||||
|
？
┭┮﹏┭┮
2023-10-18 20:26
1楼
| ||||
【题目描述】
在一条长为$n$的线段上，给定m个闭区间$[a_i,b_i]$和$m$个整数$c_i$。你需要构造一个整数集合$Z$，使得$\forall i\in[1,n]$，$Z$中满足$a_i\leq x\leq b_i$的整数$x$不少于$c_i$个。求这样的整数集合$Z$最少包含多少个数。
【输入格式】
第1行，两个整数$n$和m。
接下来$m$，每行三个整数$a_i,b_i,c_i$。
【输出格式】
一行，一个整数表示最少包含的数的个数。
【样例输入】
11 5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
【样例输出】
6
【数据范围与约定】
$1\leq n,m\leq 50000,0\leq a_i,b_i\leq 50000,1\leq c_i\leq b_i-a_i+1$
【来源】
《算法竞赛进阶指南》