CF1949E.Damage per Second

你刚刚在你最喜欢的角色扮演游戏中创建了一个新角色，现在需要决定如何分配技能点。

你需要选择的两个技能属性是：每击伤害和每秒攻击次数。每击伤害表示你每次攻击造成的伤害值，每秒攻击次数表示你每秒可以攻击的次数。初始时，这两个技能属性都为 $0$。你有 $k$ 个技能点可以自由分配；换句话说，你可以选择这两个技能的值，使它们都是正整数且它们的和不超过 $k$。

游戏的教程（你想尽快完成的无聊部分）包含 $n$ 个怪物，需要依次击杀。第 $i$ 个怪物有 $h_i$ 点生命值，也就是说，你对它造成的总伤害至少达到 $h_i$ 时，它就会死亡。

你应该如何分配这两个技能属性，才能最小化击杀所有 $n$ 个怪物所需的总时间？

第一行包含两个整数 $n$ 和 $k$（$1\leq n\leq 200\,000$，$2\leq k\leq 200\,000$）——敌人的数量和可分配的技能点数。

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

输出两个正整数 $x$ 和 $y$（$1\le x, y$ 且 $x+y\le k$）——你想分配到每击伤害和每秒攻击次数上的技能点数。如果有多组最优解，输出任意一组均可。

在第一个样例中，只有一个怪物，你有 $7$ 个技能点可以分配。如果你将 $3$ 点分配给每击伤害，则需要 $5$ 次攻击才能击杀它。如果你将 $4$ 点分配给每秒攻击次数，则需要 $1.25$ 秒来击杀怪物。没有办法比这更快地击杀怪物了。

在第二个样例中，你可以对每个怪物只需攻击一次，总共只需 $0.8$ 秒。如果你将 $4$ 点分配给每击伤害，剩下的 $5$ 点分配给每秒攻击次数即可。

由 ChatGPT 4.1 翻译