2030: 宝典2第七章广告问题
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:8
Solved:7
Description
【题目描述】广告问题(ad.cpp/c/pas)uva10148 Advertisement
“你知不知道,在未来,你将要领导我们去对抗这世界上最庞大的黑暗势力?可是你却在这里贴小广告?一点没有身为领导者的觉悟啊。”李旭琳一副恨铁不成钢的表情。
“哈,像我这么普通的魔法学徒,满大街都是,就算是真的,你也应该早点穿越过来啊,你这么晚才来,能来得及吗?”小墨老师站在魔法世界最繁华的商业街上东张西望。
“一切皆有可能,只要肯努力,任何时候学习都来得及。这是未来的你一直教导我们的。”李旭琳继续坚持。
“好了好了,先贴广告吧,完不成任务,中午广告商不给盒饭吃的。”小墨老师开始埋头工作了。
已知广告商要求小墨老师调查了n (1≤K≤1000)位顾客,这n位顾客每天都有固定的活动区间,每段区间至少要贴k (1≤K≤1000)个广告,广告商要求小墨老师在这些区间贴广告,问如何贴广告使其数量最少。
【输入格式】
第一行为一个整数,表示测试数据的组数。每组数据的第一行为k和n。随后n行为区间的左右端点。
【输出格式】
第一行为一个整数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