给定牌编号为 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 。若存在多种合法方案,可以输出任意一种。每一次查询相互独立。