题解：P17292 [Algo Beat Contest 013 & MSOI R2] 告诉我

lailai0916 · 2026-08-31 08:53:14 · 题解

题意简述

有两个初值为 0 的计数器。每消耗一点能量，两个计数器同时加一；第一个计数器每到达 a 的倍数便贡献一级。第二个计数器不小于 c 时，可以额外贡献一级，并将两个计数器清零。

求消耗 x 点能量最多能获得多少级。

解题思路

每次触发高级保底，两个计数器都会清零。因此，任意策略都能唯一划分为若干个完整段和最后的剩余段。完整段长度至少为 c，并额外贡献一级；剩余段不触发高级保底。

长度为 l 的完整段贡献 \lfloor l/a\rfloor+1 级，剩余段贡献 \lfloor l/a\rfloor 级。

设 c=pa+r，其中 0\le r<a。

固定高级保底触发 k 次。先把每个完整段设为最短长度 c。这样消耗 kc 点能量，并获得 k(p+1) 级。尚未分配的能量为：

若 r=0，所有完整段恰好停在常规保底边界。此后无论把能量分配给哪个段，每增加一个常规等级都需要 a 点能量。因此：

此时每增加一次高级触发都会多得一级，故取 k=\lfloor x/c\rfloor 最优。

下面设 r>0，并记 b=a-r。每个最短完整段已经积累了余数 r。向该段再分配 b 点能量，就能获得一个常规等级。每个完整段恰有一次这种低价补全机会，共有 k 次。

用完这些机会后，任何额外常规等级都需要完整的 a 点能量。交换分配顺序不会改变可行性，所以最优策略一定先使用低价补全。

因此应先完成尽可能多的低价补全。令：

固定 k 时的最优答案为：

该式既是上界，也能通过先补全 t 个完整段达到。因此，它就是固定触发次数后的最优值。

记 d=c+b=(p+1)a。若 k\le\lfloor x/d\rfloor，剩余能量足够补全每个完整段。代入上式并合并剩余的整组 a 可得：

所以前一段关于 k 单调递增，其最优点为 \lfloor x/d\rfloor。

若 k>\lfloor x/d\rfloor，就无法完成全部低价补全。此时 t=\lfloor e/b\rfloor<k，补全后的余量又小于 b\le a。因此：

相邻两项之差可以写为：

其中 \delta_k 只可能是 \lfloor c/b\rfloor 或 \lceil c/b\rceil。比较 (p+1)b 与 c：前者较小时，所有相邻差均非正；前者较大时，所有相邻差均非负；相等时，所有相邻差均为零。故后一段也单调，最优点只能在端点。

综上，只需计算以下至多四个触发次数：

其中第三个数只有不超过 \left\lfloor\frac{x}{c}\right\rfloor 时才合法。算法只计算常数个候选点，时间复杂度为 O(1)，空间复杂度为 O(1)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
ll get(ll a,ll c,ll x,ll k)
{
    ll p=c/a,r=c%a,e=x-k*c;
    ll ans=k*(p+1);
    if(!r)return ans+e/a;
    ll b=a-r,t=min(k,e/b);
    return ans+t+(e-t*b)/a;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a,c,x;
    cin>>a>>c>>x;
    ll d=(c/a+(c%a!=0))*a;
    array<ll,4> q={0,x/d,x/d+1,x/c};
    ll ans=0;
    for(auto k:q)if(k<=x/c)ans=max(ans,get(a,c,x,k));
    cout<<ans<<'\n';
    return 0;
}