A16688. Loyalty
编程题
普及/提高-
知识点
题目描述
你是一家商店的顾客，想要购买 $n$ 件商品。每件商品 $i$ 的价格为 $a_i$，其中 $1 \leq a_i \leq X$，$X$ 是忠诚度因子。
你在商店的忠诚度等级被定义为 $\lfloor \dfrac{S}{X} \rfloor$，其中 $S$ 是截至目前为止已购买商品的总花费。初始时，$S = 0$。
如果你购买价格为 $p$ 的商品，并且本次购买导致你的忠诚度等级提升，那么你能够获得 $p$ 的奖励点数。
你的任务是，通过选择商品的最佳购买顺序，使奖励点数最大，并输出最大能获得的奖励点数及对应的购买顺序。
你在商店的忠诚度等级被定义为 $\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 \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$ 个整数——表示最佳购买顺序下的商品价格。
如果有多种顺序都能获得最大奖励点数，可以输出其中任意一种。
第一行输出一个整数——在最佳购买顺序下，最多能获得的奖励点数。
第二行输出 $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
说明/提示
在第一个测试用例中：
1. 购买第一个商品后 $S = 1$，忠诚度等级为 0；
2. 购买第二个商品后 $S = 3$，此时忠诚度等级变为 $1$，获得 $2$ 个奖励点数；
3. 购买第三个商品后 $S = 5$，忠诚度等级变为 $2$，获得 $2$ 个奖励点数；
4. 购买第四个商品后 $S = 7$，忠诚度等级变为 $3$，获得 $2$ 个奖励点数；
5. 购买第五个商品后 $S = 9$，忠诚度等级变为 $4$，获得 $2$ 个奖励点数；
6. 购买第六个商品后 $S = 11$，忠诚度等级变为 $5$，获得 $2$ 个奖励点数；
7. 购买第七个商品后 $S = 12$，忠诚度等级变为 $6$，获得 $1$ 个奖励点数；
8. 购买第八个商品后 $S = 13$；
9. 购买第九个商品后 $S = 14$，忠诚度等级变为 $7$，获得 $1$ 个奖励点数；
10. 购买第十个商品后 $S = 15$。
共获得 $12$ 个奖励点数。
在第二个测试用例中：
1. 前四件商品购买后 $S = 8$，忠诚度等级为 0；
2. 购买最后一件商品后 $S = 13$，忠诚度等级变为 $1$，获得 $5$ 个奖励点数。
在第三个测试用例中：
1. 前八件商品购买后 $S = 20$，忠诚度等级为 0；
2. 购买第九件商品后 $S = 30$，忠诚度等级变为 $1$，获得 $10$ 个奖励点数；
3. 购买第十件商品后 $S = 51$，忠诚度等级变为 $2$，获得 $21$ 个奖励点数；
4. 购买第十一件商品后 $S = 73$，忠诚度等级变为 $3$，获得 $22$ 个奖励点数。
1. 购买第一个商品后 $S = 1$，忠诚度等级为 0；
2. 购买第二个商品后 $S = 3$，此时忠诚度等级变为 $1$，获得 $2$ 个奖励点数；
3. 购买第三个商品后 $S = 5$，忠诚度等级变为 $2$，获得 $2$ 个奖励点数；
4. 购买第四个商品后 $S = 7$，忠诚度等级变为 $3$，获得 $2$ 个奖励点数；
5. 购买第五个商品后 $S = 9$，忠诚度等级变为 $4$，获得 $2$ 个奖励点数；
6. 购买第六个商品后 $S = 11$，忠诚度等级变为 $5$，获得 $2$ 个奖励点数；
7. 购买第七个商品后 $S = 12$，忠诚度等级变为 $6$，获得 $1$ 个奖励点数；
8. 购买第八个商品后 $S = 13$；
9. 购买第九个商品后 $S = 14$，忠诚度等级变为 $7$，获得 $1$ 个奖励点数；
10. 购买第十个商品后 $S = 15$。
共获得 $12$ 个奖励点数。
在第二个测试用例中：
1. 前四件商品购买后 $S = 8$，忠诚度等级为 0；
2. 购买最后一件商品后 $S = 13$，忠诚度等级变为 $1$，获得 $5$ 个奖励点数。
在第三个测试用例中：
1. 前八件商品购买后 $S = 20$，忠诚度等级为 0；
2. 购买第九件商品后 $S = 30$，忠诚度等级变为 $1$，获得 $10$ 个奖励点数；
3. 购买第十件商品后 $S = 51$，忠诚度等级变为 $2$，获得 $21$ 个奖励点数；
4. 购买第十一件商品后 $S = 73$，忠诚度等级变为 $3$，获得 $22$ 个奖励点数。