广告问题
成绩 | 100 | 开启时间 | 2020年02月20日 星期四 19:50 |
折扣 | 0.8 | 折扣时间 | 2020年02月20日 星期四 19:50 |
允许迟交 | 是 | 关闭时间 | 2020年02月20日 星期四 19:50 |
输入文件 | ad.in | 输出文件 | ad.out |
【题目描述】广告问题(ad)UVA 10148 Advertisement
广告商调查了n(1≤n≤1 000)位顾客,这n位顾客每天都有固定的活动区间,每段区间至少要贴k(1≤k≤1 000)个广告,若区间不够放k个广告,则该区间全部填满,广告商要在这些区间贴广告,问如何贴广告使其数量最少。
【输入格式】
第一行为一个整数,表示测试数据的组数。每组数据的第一行为k和n,随后n行为区间的左右端点,左右端点的绝对值不超过10 000。
【输出格式】
第一行为一个整数m,表示最少广告数,随后m行为广告的位置。
【输入样例】
1
5 10
1 10
20 27
0 -3
15 15
8 2
7 30
-1 -10
27 20
2 9
14 21
【输出样例】
19
-5
-4
-3
-2
-1
0
4
5
6
7
8
15
18
19
20
21
25
26
27