ABC415D题解

Awsdkl · 2025-07-21 08:14:46 · 题解

贪心。

不难想到，先在 A_i - B_i 最小的店换是最优的。这样每次换后可乐减少的量也是最小的，那么能换的次数也是最多的。

可以按照 A_i - B_i 的值从小到大排序，能换就换。然后考虑在一个店最多喝到多少。由于每次换都是 N \gets N - A_i + B_i，则每次可以换的次数就是 \lfloor \frac{N-A_i}{A_i - B_i} \rfloor + 1，我们令 D_i = A_i - B_i，则式子为 \lfloor \frac{N-A_i + D_i}{D_i} \rfloor。则在当前店换的次数为 \lfloor \frac{N-A_i + D_i}{D_i} \rfloor，换完后将 N 更新为 N - \lfloor \frac{N-A_i + D_i}{D_i} \rfloor \times D_i。

记得不要见祖宗。

代码

#include<bits/stdc++.h>
using namespace std;
#define int ll
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pipii;
const int MAXN = 2e5+5;

ll n, m;
pipii shop[MAXN];
ll ans;

signed main()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%lld%lld", &shop[i].second.first, &shop[i].second.second);
        shop[i].first = shop[i].second.first - shop[i].second.second;
        // shop[i].first 就是上文所说的 D
    }
    sort(shop + 1, shop + m + 1);
    for(int i = 1;i <= m;i++)
    {
        if(n < shop[i].second.first) continue;
        ans += (n - shop[i].second.first + shop[i].first) / shop[i].first;
        n = n - ((n - shop[i].second.first + shop[i].first) / shop[i].first) * shop[i].first;
    }
    printf("%lld", ans);
    return 0;
}