← 返回题目

题库练习 Loyalty

← 上一题下一题 →

A16688 | $Loyalty$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

你是一家商店的顾客，想要购买 $n$ 件商品。每件商品 $i$ 的价格为 $a_i$，其中 $1 \leq a_i \leq X$，$X$ 是忠诚度因子。 你在商店的忠诚度等级被定义为 $\lfloor \dfrac{S}{X} \rfloor$，其中 $S$ 是截至目前为止已购买商品的总花费。初始时，$S = 0$。 如果你购买价格为 $p$ 的商品，并且本次购买导致你的忠诚度等级提升，那么你能够获得 $p$ 的奖励点数。 你的任务是，通过选择商品的最佳购买顺序，使奖励点数最大，并输出最大能获得的奖励点数及对应的购买顺序。

输入格式

每个测试包含多组测试用例。第一行为测试用例的数量 $t$（$1 \le t \le 2 \cdot 10^4$）。之后是每个测试用例的描述。 每个测试用例的第一行为两个整数 $n$（$1 \leq n \leq 10^5$）和 $X$（$1 \leq X \leq 10^9$），分别表示商品数量和忠诚度因子。 每个测试用例的第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （$1 \leq a_i \leq X$），表示每个商品的价格。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

每个测试用例输出两行。 第一行输出一个整数——在最佳购买顺序下，最多能获得的奖励点数。 第二行输出 $n$ 个整数——表示最佳购买顺序下的商品价格。 如果有多种顺序都能获得最大奖励点数，可以输出其中任意一种。

输入输出样例

输入 #1

7
10 2
1 2 1 2 1 2 1 2 1 2
5 10
2 2 2 2 5
11 23
5 5 22 1 21 2 10 3 1 1 2
1 1
1
1 17
11
3 100
44 32 1
16 100500
42801 73112 95296 68791 42217 21871 29316 84405 24273 42894 63370 53473 57156 61369 80 27290

输出 #1

12
1 2 2 2 2 2 1 1 1 1
5
2 2 2 2 5
53
1 1 5 2 1 2 5 3 10 21 22
1
1
0
11
0
44 32 1
503499
53473 42894 80 57156 42801 61369 42217 63370 29316 68791 27290 73112 24273 84405 21871 95296

C++ 编辑器

输入

输出