题解：P13013 [GESP202506 五级] 奖品兑换

· · 题解

简单的二分题目，但是还是有许多需要注意的点的（就是有点玄学）。

我们容易发现，总可兑换的奖品份数是一个关于方案一兑换奖品份数单峰的函数，于是可以用二分或者三分。

但是，这里虽然单峰，但是可能会存在平台的问题，所以用二分就不一定能够找到最优解了，这个时候用三分就合适不少。由于这里平台最多只有两个整数的长度，直接选择拿两个三等分点三分就比较省事。

但是这样的三分对于极小范围是不一定能够较好地解决的（小范围上面的情况还是比较容易遇到），所以直接暴力计算小范围即可（反正主打一个结合了暴力算法和非暴力算法）。

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

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    int l=0,r=min(n/a,m/b);
    while(r-l>500)
    {
        int m1=l+(r-l)/3;
        int m2=r-(r-l)/3;
        int f1=m1+min((n-a*m1)/b,(m-b*m1)/a);
        int f2=m2+min((n-a*m2)/b,(m-b*m2)/a);
        f1<f2?l=m1:r=m2;
    }
    int best=0;
    for(int k=l;k<=r;k++)
    {
        int t=min((n-a*k)/b,(m-b*k)/a);
        if(k+t>best)best=k+t;
    }
    cout<<best;
    return 0;
}