1901. 养秋

考点:贪心+小模拟。

  1. 显然,购买了秋之后,越晚卖越好,即总是在第 23 天卖出。易证这样做比更早卖出更优。
  2. 设在第 i 天购入秋,则该秋利润为 23-i+1 天每天贡献一点,且卖出能回 6 点。故若价格低于 23-i+1+6,证明当前购入秋是赚的。
  3. 显然如果能购入的话,越早购入越好。因此策略是每一天一开始贪心地买秋,直到发现不赚了或不够钱为止。
  4. 由于 11c^{25+n}=2\times11c^n,解方程得 c=2^{\frac1{25}}。最坏情况下,不赚钱时有 11\times 2^{\frac n{25}}=23+6 解得 n\approx 35,故无论如何最多只需要购买约 35 个秋,可以用枚举法实现本题。

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll mn = 40, days = 23; ll g[mn], blue = 25, profit, h; ll price() { return 11 * pow(2, 1. * h / 25); } ll f(ll n) { return 20 * (1 <= n && n <= 6) + 35 * (7 <= n && n <= 12) + 50 * (13 <= n && n <= 18) + 80 * (19 <= n); } signed main() { cin.tie(0)->ios::sync_with_stdio(false); for (ll i = 1; i <= days; ++i) { cin >> g[i]; } for (ll i = 1; i <= days; ++i) { ll expect = (days - i + 1) + 6; //还能赚多少 while (blue >= price() && price() < expect) //够钱买,能赚钱 { blue -= price(); profit -= price(); ++h; } blue += h + f(i) + g[i]; profit += h; } profit += 6 * h; cout << profit; return 0; }