题解：P14974 [USACO26JAN1] Chip Exchange B

· · 题解

为什么感觉这场比赛 C<A<<<<<B 呢？本来估计可以 AK 然后直接飞升 Silver 的，结果被 B 神秘 Ad-hoc 创飞了 /fn

博客园 USACO 2026 Jan1 Bronze

以下记“B->A”为把 B 换成 A。

题目要求的是 A，你首先想着 B->A 能不能多增加。首先显然是把能换的都换了。

然后既然收到的芯片是随机的，所以肯定是运气最坏的情况，直观理解就是，你收到的芯片换成目标芯片 A 是最不值的那一种。所以就要分类讨论：

  1. 如果 B 换成 A 不亏不赚（c_A=c_B），那么最坏情况就是先给你一大堆 B，恰好可以全部换成 A；等到 A 差一次交换的就达到 f_A 的时候，把 A 补到 f_A-1，剩下这一个 A 肯定就是给你 c_B 个 B，让你用 c_B 个 B 换成 c_A 个 A。
  2. 如果 B 换成 A 会亏（c_B>c_A），那么最坏情况就应该是给芯片 B 要多一点，先给一大堆 B，用这些 B 恰好完全换成 A；等到 A 差一次交换的就达到 f_A 的时候，就把 A 补到 f_A-1，剩下这一个 A 同理情况 1，给你 c_B 个 B，让你用 c_B 个 B 换成 c_A 个 A。
  3. 如果 B 换成 A 会赚（c_B<c_A），那最坏情况：一直给 A 到达到 f_A 之前 1 个，然后给 B 补充到 c_B 个，用这 c_B 个 B 去换 c_A 个 A。

难点在于就是分类讨论，剩下的式子应该很好推，简单模拟即可。难度黄左右。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=-1;
ll a,b,ca,cb,f;
ll cnt=0;  //交换次数
inline void changeall()
{
    cnt=(b/cb); b-=cnt*cb,a+=cnt*ca;
}
inline ll solve()
{
    cin>>a>>b>>ca>>cb>>f;
    ll ans=0;
    changeall();
    if(a>=f) return 0;
    cerr<<a<<' '<<b<<endl;
    if(ca==cb)
    {
        cnt=(f-a)/ca; if((f-a)%ca==0) cnt--;
        ans+=cnt*cb-b; b+=cnt*cb-b;
        changeall();
        // cerr<<cnt<<' '<<a<<' '<<b<<endl;
        ans+=(f-a-1);
        ans+=cb;
    }
    else if(cb>ca)
    {
        cnt=(f-a)/ca; if((f-a)%ca==0) cnt--;
        ans+=cnt*cb-b; b+=cnt*cb-b;
        changeall();
        ans+=(f-a-1);
        ans+=cb;
    }
    else
    {
        ans+=(f-a-1);
        ans+=cb-b;
    }
    return ans;
}
int main()
{
    // freopen("neuvillette.in","r",stdin);
    // freopen("neuvillette.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--) cout<<solve()<<'\n';
    return 0;
}
/*
- 标题 『Problem 1. Chip Exchange』 
- 链接 『https://usaco.org/index.php?page=viewproblem&cpid=1527&lang=en』
- 时限 『4000 ms』
- 用时 『h 40min』
- 思路：
题目要求的是A，看看cb B->ca A能不能多增加

先把能换的都换了，更新a,b

假如B换成A不亏不赚，那最坏情况应该就是先给你一大堆B可以全部换成A，等到A差一点点的时候又给你一大堆B
aA bB cB->cA fA
然后补B，补充到floor((f-a)/c)*c，全部变成A，更新a,b=0
然后给A：(f-a-1)
然后给B：c，换成A

假如B换成A会亏(cb>ca)，那最坏情况应该就是给一大堆B，然后用这些B换成A，换到再换一次A就达标了为止
B恰好完全反应，给A,更新a,b=0
然后给A补到达标-1，给Bcb个

假如B换成A会赚(cb<ca)，那最坏情况：一直给A到达标之前1个，然后给B (cb-b) 个，用B去换A
*/