爱你没差 题解

· · 题解

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

根据样例中的情形，猜测可以优先合并较小数。事实上容易发现若每次操作合并当前最小的两个数，当且仅当最小的 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);