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

Solution

一道贪心和二分题，本人没场切，只拿了暴力分，回来补篇题解。

我们可以把这个过程看成先进行很多次第一种兑换，再将其中的一部分第一种兑换替换为第二种兑换先进行

k

次第一种兑换，那么课堂优秀券还剩

n-ak

，作业优秀券还剩

m-bk

。

将一次第一种兑换更改为第二种，也就是原来的

-a,-b

变成了

-b,-a

，可以看作是将

b-a

张课堂优秀券转化成了

b-a

张作业优秀券。

所以我们可以进行很多次第一种兑换，即使把作业优秀券兑换成了负数也没关系，可以用剩下的课堂优秀券进行转化。

即：

n - ak ≥0

n - ak ≥ bk - m

k=\min(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{n+m}{a+b} \rfloor)

之后可以将

n,m

互换，整个过程用二分进行优化。

当然有听说有

O(1)

做法的更好可以参考。

AC code

CPP

#include <bits/stdc++.h>
using namespace std;
long long n,m,a,b,l,r;
int check(int v) 
{
    long long x,y,t;
    x=v*a;
    y=v*b;
    if(y>m)
    {
        t=(y-m+(b-a)-1)/(b-a);
        y-=t*(b-a);
        x+=t*(b-a);
    }
    return x<=n&&y<=m;
}
int main() 
{
    cin>>n>>m>>a>>b;
    if(a>b) swap(a,b);
    if(n>m) swap(n,m);
    if(a==b)
    {
        cout<<n/a;
        return 0;
    }
    l=0,r=n;
    while(l<r) 
    {
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<r;
    return 0;
}

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

文章操作

Solution

AC code

相关推荐

评论

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