给定牌编号为 1…n(第 i 张牌数字为 i),对每个查询给出整数 k,要求从这些牌中选出若干张使其数字之和为 k,并输出所选牌的编号(升序)。若无解输出 -1。各次查询互不影响。
核心思想:利用连续整数集合 {1,2,…,n} 的贪心可表示性。记前缀和 S=n(n+1)/2。若 k>S,无论如何都无法得到 k,直接输出 -1。 当 k≤S 时,从大到小扫描 i=n…1,若 k≥i 就选 i,并令 k←k−i。由于 {1,…,n} 连续且互不相同,贪心(每次尽量取不超过剩余 k 的最大数)一定能在 k≤S 时构造出一个解;当扫描结束必然得到 k=0。这是一个“标准币值为 1..n 的找零问题”,该体系是规范(canonical)的,贪心正确。
实现要点:
Tk 有 n 张卡牌,编号为 1 ~ n ,其中编号 i 的卡牌上写着数字。接下来有 m 次查询,每次给出一个整数 k 。你需要从这 n 张卡牌中选出若干张,使得这些卡牌上的数字之和等于 k ;
将你选择的卡牌编号按从小到大输出。若无解,输出 −1 。若存在多种合法方案,可以输出任意一种。每一次查询相互独立。
每个测试文件均包含多组测试数据。
第一行输入一个整数 T(1≤T≤104) 代表数据组数,每组测试数据描述如下:
第一行输入两个整数 n,m(1≤n,m≤2×105),分别表示卡牌数量与查询次数;
此后 m 行,每行输入一个整数 k(1≤k≤1012) 表示本次查询所需的目标和。
除此之外,保证单个测试文件中所有数据组的 n×m 之和不超过 2×106
对于每一组测试数据,依次输出 m 个查询的答案:
若存在解,先输出一行一个整数,表示选择的卡牌数量;随后新起一行,按从小到大输出所选卡牌的编号,编号之间用一个空格分隔;
若无解,输出 −1 。
如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
输入
2
5 3
1
9
16
3 4
6
2
5
7
输出
1
1
3
2 3 4
-1
3
1 2 3
1
2
2
2 3
-1
说明
在第一组测试数据中:
当 k=1 时,选择编号 {1} 即可;
当 k=9 时,选择编号 {2,3,4} 的卡牌之和为 9 ;
当 k=16 时,1 ~ 5 的卡牌数字总和为 15 ,不足以得到 16,因此无解。