AGC019: A - Ice Tea Store
問題
普通の解法
0.25L のものを奇数個購入することはあり得ない。よって、0.25L は偶数個購入する必要があるが、これは0.5Lのものと値段と比較して小さい方を用いれば良い。同様のことが0.5Lと1Lの関係も言える。1Lと2Lの関係について、1Lの方が安くなるとき、答えはである。また、2Lのもののほうが1Lの最小価格と比較して単価が安いとき、偶数奇数で場合分けして買えるだけ2Lを買い、余ったら1Lを1つ買うことになる。
int main() { int64_t Q, H, S, D, N; cin >> Q >> H >> S >> D >> N; auto precost = min(2 * Q, H); auto cost = min(2 * precost, S); cout << min(N * cost, N / 2 * D + (N % 2 == 1 ? cost : 0)) << "\n"; }
頭がない解法
貪欲法 + 全探索 で解いてしまった。
大抵は1Lあたりの単価が安いものを優先的に買うのが都合が良いため、 分に貪欲法を適用する。 残りの は全探索をすれば良い。この計算は の計算量で抑えられるため、十分間に合う。
int64_t Q, H, S, D, N; int64_t const Alpha = 2; pair<int64_t, double> greedy(int64_t M) { vector<pair<int64_t, int64_t>> vs{{Q, 1}, {H, 2}, {S, 4}, {D, 8}}; sort(vs.begin(), vs.end(), [](auto const &l, auto const &r) { return l.first * r.second < r.first * l.second; }); int64_t cost, perL; tie(cost, perL) = vs[0]; auto buynum = (4 * M + perL - 1) / perL; return {buynum * cost, M + Alpha - (buynum * perL / 4.0)}; } int64_t bf(double r) { auto constexpr MAX = std::numeric_limits<int64_t>::max(); if (r == 0) return 0; if (r < 0) return MAX; auto a = bf(r - 0.25); if (a < MAX) a += Q; auto b = bf(r - 0.5); if (b < MAX) b += H; auto c = bf(r - 1.0); if (c < MAX) c += S; auto d = bf(r - 2.0); if (d < MAX) d += D; return min({a, b, c, d}); } int main() { cin >> Q >> H >> S >> D >> N; if (N <= Alpha) { cout << bf(N) << endl; exit(0); } int M = N - Alpha; auto x = greedy(M); auto y = bf(x.second); cout << x.first + y << "\n"; }