题解 CF10E 【Greedy Change】

WarningQAQ · 2020-10-27 19:48:10 · 题解

思路：

对于一种币值 A ，我们找出一个略大于 A 仅用币值不小于 B 且小于 A 的货币表示的值 X ，

使得贪心算法在使用 A 后要用更多零碎的货币 这样，只要枚举 A 、 B ，找出最小的这样的值即可。

#include "cstdio"
int n, dat[500], res = -1;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &dat[i]);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            int cnt1 = 1, cnt2 = 0, W = dat[i] - 1, t;
            for (int k = i + 1; k <= j; k++) //非贪心做法
                cnt1 += (W / dat[k]), W %= dat[k];
            t = W = dat[i] - 1 - W + dat[j];
            for (int k = 1; k <= n; k++) //贪心做法
                cnt2 += (W / dat[k]), W %= dat[k];
            if (cnt1 < cnt2 && (res == -1 || res > t)) //判断
                res = t; 
        }
    printf("%d", res);
    return 0;
}