题解 P2001 【硬币的面值】
本题需要在明白思路的情况下再次进行优化。
当然需要进行排序，无解的情况就是最小值不为1，那因为这样的话永远得不到价格为1的。
以下的情况都是基于排序之后的情况讨论的。
首先是O(M)的算法，我们先假设1~x的价格都可以得到，那么设a[i]是小于x+2的最大整数，可知1~x+a[i]都价格都可以完成，同时硬币数量加一。这样如果常数优化好的话可以通过前8个测试点，第9,10个会超时（如果这个都能通过那就让人对洛谷神机无语了）。
其次是O(NlogN)的算法，我们发现算法一中的很多都有冗余，因为在i加1之前的运算可能会重复多次，所以我们用div进行这一项操作。这样贪心部分算法时间复杂度仅为O(N)，可以轻松通过全部数据。