专栏文章

ABC415D题解

AAwsdkl
AT_abc415_d题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miotgnem
此快照首次捕获于
2025/12/03 00:52
3 个月前
此快照最后确认于
2025/12/03 00:52
3 个月前
查看原文
贪心。
不难想到，先在 Ai−BiA_i - B_i 最小的店换是最优的。这样每次换后可乐减少的量也是最小的，那么能换的次数也是最多的。
可以按照 Ai−BiA_i - B_i 的值从小到大排序，能换就换。然后考虑在一个店最多喝到多少。由于每次换都是 N←N−Ai+BiN \gets N - A_i + B_i，则每次可以换的次数就是 ⌊N−AiAi−Bi⌋+1\lfloor \frac{N-A_i}{A_i - B_i} \rfloor + 1，我们令 Di=Ai−BiD_i = A_i - B_i，则式子为 ⌊N−Ai+DiDi⌋\lfloor \frac{N-A_i + D_i}{D_i} \rfloor。则在当前店换的次数为 ⌊N−Ai+DiDi⌋\lfloor \frac{N-A_i + D_i}{D_i} \rfloor，换完后将 NN 更新为 N−⌊N−Ai+DiDi⌋×DiN - \lfloor \frac{N-A_i + D_i}{D_i} \rfloor \times D_i。
记得不要见祖宗。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...