为什么贪心不可取?
查看原帖
为什么贪心不可取?
675208
coder2009楼主2023/6/10 18:48

rt,是否可以证明贪心思路一定会出现反例

void best_coder() {
    long long n, a, b, c, d;;
    cin >> n >> a >> b >> c >> d;
    double t = b * 1.0 / a;
    double k = d * 1.0 / c;
    long long ans = 0;
    if (t < k) {
        ans += n / a * b;
        n -= n / a * a;
        if (n > 0) {
            if (n < c) {
                ans += b;
                cout << ans;
                return;
            }
            ans += min(n / c * d, b);
        }
    } else {
        ans += n / c * d;
        n -= n / c * c;
        if (n > 0) {
            if (n < a) {
                ans += d;
                cout << ans;
                return;
            }
            ans += min(n / a * b, d);
        }
    }
    cout << ans;
}
2023/6/10 18:48
加载中...