自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

搬运于2025-08-24 21:32:49，当前版本为作者最后更新于2013-12-21 22:40:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题需要在明白思路的情况下再次进行优化。

当然需要进行排序，无解的情况就是最小值不为1，那因为这样的话永远得不到价格为1的。

以下的情况都是基于排序之后的情况讨论的。

首先是O(M)的算法，我们先假设1~x的价格都可以得到，那么设a[i]是小于x+2的最大整数，可知1~x+a[i]都价格都可以完成，同时硬币数量加一。这样如果常数优化好的话可以通过前8个测试点，第9,10个会超时（如果这个都能通过那就让人对洛谷神机无语了）。

其次是O(NlogN)的算法，我们发现算法一中的很多都有冗余，因为在i加1之前的运算可能会重复多次，所以我们用div进行这一项操作。这样贪心部分算法时间复杂度仅为O(N)，可以轻松通过全部数据。