Skip to content

14278: 【原4278】熟练果

题目

题目描述

author: whj dhc 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4278

问题描述

"又到了白色相簿的季节呢", 雪菜喃喃道. 今天她有些悲伤, 不是因为三人不能永远在一起, 而是因为种在自家院子里还没来得及采集的熟练果就要因为寒冷而坏掉了. 熟练果是雪菜重要的经济来源, 所以她必须要尽快抢救剩下的果实.

熟练果是一种娇贵的果实, 大小不一, 且无法用普通的方法收集, 只能使用一种特殊的装置——熟练果采集机.

熟练果采集机是一种专一的机器, 每一台机器只能采集一种尺寸的熟练果, 而且在设置好这个尺寸后永远都不能改变.

熟练果采集机也是一种怕寂寞的机器, 如果有同伴去工作但自己却留下就会感到无聊, 因此所有机器在同一天必须同时工作.

现在地里还剩了$n$个熟练果, 第$i$个的尺寸是$a_i$. 雪菜购置了$k$台熟练果采集机, 她想要收集到尽量多的熟练果(换言之, 要让这$k$台机器同时工作尽量多的天数). 在此基础上, 她还想要让收集到的所有熟练果尺寸之和最大.

请你帮帮雪菜, 设置好这$k$台机器要采集的尺寸, 并将这些尺寸从大到小输出.

一句话题意: 给定$n, k, a_i, \cdots, a_n$, 记可重集合$A = {a_1, \cdots, a_n}$, 求可重集合$S \subseteq A$, $|S| = k$, 使得满足$\bigcup_{i=1}^{x} S \subseteq A$的$x$最大化. 如果存在多个这样的$S$, 输出元素之和最大的一个, 并将$S$的所有元素按从大到小输出.

输入格式

n k
a_1 a_2 ... a_n

输出格式

一行, $k$个数, 从大到小排列, 代表每台机器设置的尺寸, 用空格隔开.

样例输入1

9 3
1 2 3 7 3 2 1 3 6

样例输出1

3 2 1

样例输入2

15 2
1 2 1 1 1 2 1 1 2 1 2 1 1 1 1

样例输出2

1 1

数据范围与约束

对于所有的测试点, $n \le 10^5, k \le 10^5, 0 \le a_i \le 10^9$.

部分测试点满足特性如下:

| 测试点 | n | k | a_i | | ------ | ---- | ------- | ---------- | | 1~2 | | $= 1$ | | | 3 | $\le 10$ | | $\le 10^5$ | | 4~7 | | | $\le 10^5$ | | 8~10 | | ||

HINT

如果你想要排序, 可以通过如下方法实现:

  • 包括头文件algorithm
  • 在命名空间内有sort(begin, end)函数, 其中begin和end分别为排序开始的位置和结束的位置(左闭右开). 特别地, 如果想要让arr数组中下标为i至下标j之间(左闭右开)的元素从小到大排列的话, 可以调用sort(arr + i, arr + j)

例如:

#include <algorithm>
using namespace std;
int a[] = {3, 4, 1, 2};
int main() {
    sort(a + 1, a + 3);
    // 此时 a = {3, 1, 4, 2}
    sort(a, a + 4);
    // 此时 a = {1, 2, 3, 4}
    return 0;
}

需要注意的是,禁止使用<algorithm>库内的其他函数.

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！