01_Milk Pails

问题描述

USACO 2016 February Contest, Bronze Problem 1. Milk Pails https://usaco.org/index.php?page=viewproblem2&cpid=615

给定 X, Y, M ，求 aX + bY 不超过 M 的最大值，a, b 任意。

样例

输入

17 25 77

输出

76

思路

a 的范围为 0 至 M/X ，b 的范围为 0 至 M/Y 。 遍历 a 和 b ，如果 aX + bY 不超过 M ，则 ans 更新为最大值。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("pails.in", "r", stdin);
    freopen("pails.out", "w", stdout);
    int x, y, m;
    cin >> x >> y >> m;
    int ans = 0;
    for(int i = 0; i <= m / x; i++){
        for(int j = 0; j <= m / y; j++){
            int now = i * x + j * y;
            if(now <= m){
                ans = max(now, ans);
            }
        }
    }
    cout << ans;
    return 0;
}