题解 | 硬币凑钱

#include <iostream>
using namespace std;

int main() {
    int n ;
    cin >> n;
    int ans = n;
    if(n <= 70){
        int now = 0;
        for(int i = 0; i <= n/7; i ++){
            for(int j = 0; j <= (n - i * 7) / 5; ++ j){
                now = i + j + (n - 7 * i - 5 * j);
                ans = min(ans, now);
                
            }
        }
    }
    else {
        int cnt = (n - 70)/7;
        n = n - cnt * 7;
        int now = 0;
        for(int i = 0; i <= n/7; i ++){
            for(int j = 0; j <= (n - i * 7) / 5; ++ j){
                now = i + j + (n - 7 * i - 5 * j);
                ans = min(ans, cnt + now);
                
            }
        }
    }
    cout << ans << '\n';
}
// 64 位输出请用 printf("%lld")

事实上在每个面额组成的最大公倍数之外的部分一定是选择最大面额最优，然后剩下的部分暴力求解即可