【題解】UVA-12325 Zombie’s Treasure Chest

#include <iostream>
#include <cmath>
using namespace std;
int T;
long long N, S1, V1, S2, V2, ans;

int main() {
    cin >> T;
    for (int Case = 1; Case <= T; Case++) {
        cin >> N >> S1 >> V1 >> S2 >> V2;
        ans = 0;
        //先考慮至少有一種寶石的size很大，可以減少枚舉的時間
        if (S1 > sqrt(N)) {
            // 枚舉第一種寶石，O(N/S1) < O(sqrt(N))
            for (int i = 0; S1 * i <= N; i++){
                ans = max(ans, V1*i + (N - S1*i) / S2 * V2);
            }
        } else if (S2 > sqrt(N)) {
            // 枚舉第二種寶石，O(N/S2) < O(sqrt(N))
            for (int i = 0; S2 * i <= N; i++){
                ans = max(ans, V2*i + (N - S2*i) / S1 * V1);
            }
        } else {
            // 如果兩種寶石的size都很小，枚舉CP較差的那種
            if (V1*S2 < V2*S1){
                swap(S1, S2);
                swap(V1, V2);
            }
            // 枚舉size為S2的寶石，最多以不超過S1顆為限(空間 < S2*S1)
            // 否則 S1*V2 < S2*V1，應改改拿較多size為S1的寶石
            for (int i = 0; i < S1; i++){
                ans = max(ans, V2*i + (N - S2*i) / S1 * V1);
            }
        }
        cout << "Case #" << Case << ": " << ans << "\n";
    }
    return 0;
}