CF 1860 B

Fancy Coins

这道题使用贪心。

先使用a1个常规硬币，补足m%k的金额，不够的使用花色硬币补上，并最大化a1硬币的价值。再计算剩余需要价值为k的硬币数量，不够的使用花色硬币补足，并输出总共使用的花色硬币数量。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

ll t, m, k, a1, ak;

int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t--)
    {
        ll tot = 0;
        cin >> m >> k >> a1 >> ak;
        ll now = m;
        if(a1 < m % k)
        {
            tot += m % k - a1;
            now -= now % k;
        }
        else
        {
            now -= now % k + ((a1 - now % k) / k) * k;
        }
        if(ak * k < now)
        {
            tot += now / k - ak;
        }
        cout << tot << endl;
    }
    return 0;
}