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

前言

一道很好的二分练手题。

题目内容

题目分析

我们假设用第一种方式兑换了

x

次，用第二种方式兑换了

y

次，则总次数

k = x + y

，并且满足

a \cdot x + b \cdot y \le n

和

b \cdot x + a \cdot y \le m

，且

x

与

y

都为非负整数。

因为每次兑换至少消耗

a

张课堂优秀券和

a

张作业优秀券（当

a \le b

时），所以

ans

的上界为

\min(\lfloor n / a \rfloor, \lfloor m / a \rfloor)

。

对于给定的

k

，检查是否有

x

（第一种方式兑换了

x

次，则第二种方式兑换了

k - x

次）满足：

$a \cdot x + b \cdot (k - x) \le n$
$b \cdot x + a \cdot (k - x) \le m$

整理得：

$(b-a) \cdot x \ge b \cdot k - n$ $(b > a)$
$(b-a) \cdot x \le m - a \cdot k$ $(b > a)$

计算

x

的可行区间，如果非空则

x

可行。

边界处理：

当 $a = b$ 时，直接记录答案。
当 $a < b$ 时，先计算总券数是否够，然后计算 $x$ 的区间。

上代码（知道你们直接看这个）

CPP

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define prq priority_queue

#define uns unordered_set

#define freopen freopen(".in","r",stdin);freopen(".out","w",stdout);

const int P = 998244353;

const int INF = 0x3f3f3f3f3f3f3f3f;

const int N = 1e6+10, M = 1e8 + 10;

int __lcm(int a,int b){return a/__gcd(a,b)*b;}

int n,m,a,b;
int ans=0;

signed main()
{
	fst
	cin>>n>>m>>a>>b;
	if(a>b)swap(a,b);//确保a<=b
	int l=0,r=min(n/a,m/a);//左右区间
	while(l<=r){
		int mid=(l+r)/2;
		if(a==b){
			ans=mid;
			l=mid+1;
		}//情况1
		else{
			if((a+b)*mid>n+m){
				r=mid-1;
				continue;
			}
			int mi=0;
			if(b*mid>n){
				mi=(b*mid-n+b-a-1)/(b-a);//左端点
			}
			int ma=(m-a*mid)/(b-a);
			ma=min(ma,mid);//右端点
			if(ma>=0&&mi<=ma){
				ans=mid;
				l=mid+1;
			}
            else{
                r=mid-1;
            }
		}//情况2
	}
	cout<<ans;
	return 0;
}

UPD

2025.7.2 感谢 @pika_ 大佬指出的错误。

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

文章操作

前言

题目内容

题目分析

上代码（知道你们直接看这个）

UPD

相关推荐

评论

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