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;
}