CF1344D Résumé Review

糟糕！申请科技公司的截止日期快到了，而你一直在拖延，反而去参加了各种竞赛！（我们暂且假装在当前不确定的时期里真的能找到工作。） 你已经完成了许多编程项目。实际上，编程项目一共有 $n$ 种类型，你已经完成了第 $i$ 种类型的 $a_i$ 个项目。你的简历空间有限，但你想要精心选择项目，以最大化被录用的机会。 你希望在简历中多展示同一类型的项目，以突出你的专业能力，但又不想包含太多，以免低质量项目混入。具体来说，你认为如下的量是你被录用概率的良好指标： $$ f(b_1,\ldots,b_n)=\sum\limits_{i=1}^n b_i(a_i-b_i^2)。 $$ 其中，$b_i$ 表示你在简历中包含的第 $i$ 种类型项目的数量。当然，你不能包含超过你实际完成的项目数量，因此要求 $0\le b_i \le a_i$ 对所有 $i$ 都成立。 你的简历只能容纳 $k$ 个项目，并且如果简历有空位，你绝对不会被录用，因此要求 $\sum\limits_{i=1}^n b_i=k$。 请你找到一组 $b_1,\ldots, b_n$ 的取值，使得 $f(b_1,\ldots,b_n)$ 的值最大，并满足上述两个约束条件。

第一行包含两个整数 $n$ 和 $k$（$1\le n\le 10^5$，$1\le k\le \sum\limits_{i=1}^n a_i$），分别表示编程项目的类型数和简历的容量。 第二行包含 $n$ 个整数 $a_1,\ldots,a_n$（$1\le a_i\le 10^9$），其中 $a_i$ 表示你完成的第 $i$ 种类型项目的数量。

输出一行 $n$ 个整数 $b_1,\ldots, b_n$，使得 $f(b_1,\ldots,b_n)$ 最大，并且满足 $0\le b_i\le a_i$ 且 $\sum\limits_{i=1}^n b_i=k$。如果有多组解，输出任意一组即可。 注意，你不需要输出 $f(b_1,\ldots,b_n)$ 的值。

对于第一个测试点，最优答案为 $f=-269$。注意，如果忽略 $\sum\limits_{i=1}^n b_i=k$ 的约束，可以得到更大的 $f$ 值。 对于第二个测试点，最优答案为 $f=9$。 由 ChatGPT 4.1 翻译