← 返回题目列表

Codeforces · 1949/E

E. 每秒伤害

中文机器翻译题面 查看原题

您刚刚在您最喜欢的角色扮演游戏中创建了一个新角色,现在必须决定如何培养他的技能。

需要选择的两个技能属性是:每次攻击伤害和每秒攻击次数。每次攻击造成的伤害是单次攻击所造成的伤害量,而每秒攻击次数是您在一秒钟内可以造成的攻击次数。最初,两个技能属性都设置为 $$$0$$$。您有 $$$k$$$ 技能点可以按照您的意愿分配;换句话说,你可以选择两个技能的值,使它们为正整数,且总和最多为$$$k$$$。

游戏的教程(你想尽快完成的无聊部分)由$$$n$$$个怪物组成,一个接一个地被杀死。第 $$$i$$$ 怪物拥有 $$$h_i$$$ 生命值,也就是说,它会在你造成至少 $$$h_i$$$ 伤害后死亡。

如何分配这两个技能属性以最小化杀死所有 $$$n$$$ 怪物所需的时间?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\leq n\leq200\,000$$$, $$$2\leq k\leq200\,000$$$) — 敌人的数量和技能点的数量。

第二行包含 $$$n$$$ 整数 $$$h_i$$$ ($$$1\leq h_i\leq10^{13}$$$) — 第 $$$i$$$ 个敌人的生命值。

输出

打印两个正整数 $$$x$$$ 和 $$$y$$$($$$1\le x, y$$$ 和 $$$x+y\le k$$$)——您想要投资于每次攻击伤害和每秒攻击伤害的技能点数。如果有多个最优解,则打印其中任意一个。

示例

输入 #1

1 7
14

输出 #1

3 4

输入 #2

4 9
1 2 3 4

输出 #2

4 5

输入 #3

5 13
3 4 5 6 7

输出 #3

7 6

注意

在第一个示例中,只有一个怪物,并且您有 $$$7$$$ 技能点可供分配。如果你每次击中造成 $$$3$$$ 伤害,则需要 $$$5$$$ 击中才能杀死它。如果您每秒进行 $$$4$$$ 攻击,则需要 $$$1.25$$$ 秒才能击败怪物。没有比这更快地击败怪物的方法了。

在第二个示例中,如果您将 $$$4$$$ 技能点分配给每次攻击造成的伤害,剩余 $$$5$$$ 点分配给每秒攻击次数,则每个怪物需要攻击一次,总时间为 $$$0.8$$$ 秒。