自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 23:11:06，当前版本为作者最后更新于2024-12-20 14:36:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单贪心，预估难度普及。

根据样例中的情形，猜测可以优先合并较小数。事实上容易发现若每次操作合并当前最小的两个数，当且仅当最小的 $k$ 个数之和 $S_k$ 与第 $k+1$ 小的数 $a_{k+1}$ 间满足 $mS_k<a_{k+1}$ 时不得分，且容易证明这是不得分的最少可能次数。

用小根堆维护即可做到 $O(n\log n)$。

upd 2025.3.16

看大家讨论度这么高，交的题解还几乎没有正确的证明，看来这篇题解还是写得太不够详细了。简单地把证明写好一点。

不妨假设原序列从小到大排序，$S_k=a_1+\dots+a_k$。若 $m\cdot S_k<a_{k+1}$，则一定存在一次合并，较小的数 $x\le S_k$，较大的数 $y\ge a_{k+1}$，这时必然不得分。显然对于不同的满足以上条件的 $k$，对应的合并是不同的。

然后在上述贪心过程中，当出现不得分的情况时，由 $m\cdot x<y$ 且 $m\ge2$，显然 $y$ 不可能由合并得来，否则合并成 $y$ 的两个数中至少有一个大于 $x$，不可能在 $x$ 合并之前被合并。因此 $y$ 必然是原先的某个 $a_{k+1}$，从而 $a_{k+2},\dots,a_n$ 都没有被合并。更强地，由以上的讨论，此时所有 $>m\cdot x$ 的数都不可能是合并得来的结果。则此时的 $x$ 只可能是 $a_1,\dots,a_k$ 中所有数合并的结果，即 $S_k$。

由以上证明其实我们发现可以直接排序后求出使得 $S_k<a_{k+1}$ 的 $k$ 的数量。但是时间复杂度瓶颈同样为 $O(n\log n)$，给出的序列已经排好序显得过于别有用心（误）。而且贪心更加容易猜测，作为 IOI 赛制题目难度会降低很多。

另外关于 __int128，你说的对，但是如果古老的机子除了 64 位整数就得写高精怎么办呢？std 的实现本身就没有使用 __int128，但是不可能卡。以下给出 std 的实现方法：

		x=q.top();q.pop();
		y=q.top();q.pop();
		if(y==0||x>(y-1)/m)++sum;
		q.push(x+y);