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

由于通过

n \gets n-a,m \gets m-b

和

n \gets n-b,m \gets m-a

两种方式均可兑换奖品，所以

n,m

的顺序显然是可以互换的。

暴力

显然，我们可以写出时间复杂度为

O(n)

的暴力。

大致逻辑为：每次从两种券中选择数量较多的一种，花费较多的这种券来兑换奖品。

代码如下：

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P=1e9+7;
const int N=1e5+10;
int n,m,a,b,ans;

signed main()
{
	cin>>n>>m;
	cin>>a>>b;
	if(a<b)swap(a,b);  //确保 a 较大
	while(n>=a||m>=a)
	{
		if(n<m)swap(n,m);
        if(m<b)break;    
		n-=a;
		m-=b;
		ans++;  //从n,m中选择较大的变量减去较大的花费
	}
	cout<<ans<<endl;
	return 0;
}

正解

注：下文中默认

a \ge b,n \ge m

O(n)

的暴力显然会超时，考虑进行优化。

由于每次我们都让较大的变量减少的更多，所以在进行0次或多次兑换后，

n,m

两变量的差值一定会使下次操作后

n < m

。

具体地，令

d=a-b,v= \min(n\div a,m\div b,(n-m)\div d)

，则在进行

v

次兑换后，一定会有

n-m<d

或不可再进行兑换。

当

n-m < d

时，下次操作一定会使

n < m

且

m-n < d

，于是再下次操作又会使

n > m

，以此类推。

并且在进行两次操作后，由于

n,m

均减去了

a+b

，操作后的

n-m

与开始的

n-m

大小相等。

因此，当

n-m < d

时，可以令

y=m \div (a+b)

，进行

y \times 2

次操作，具体看代码。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P=1e9+7;
const int N=1e5+10;

int n,m,a,b,ans;
int s,d;

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	cin>>a>>b;
	if(a<b)swap(a,b);
    if(a==b) //进行特判 
    {
        cout<<min(n,m)/a<<endl;
        return 0;
    }
	s=a+b,d=a-b;
	while(n>=a||m>=a)
	{
		if(n<m)swap(n,m);
		int x=(n-m)/d;
		if(x==0) //当n-m<d时 
		{
			int y=m/s;
			ans+=y*2;
			n-=y*s,m-=y*s;
			x=2;	
		}
		int v=min(n/a,min(m/b,x));
		ans+=v,n-=v*a,m-=v*b;
        if(m<b)break; //不可进行兑换 
	}
	cout<<ans<<endl;
	return 0;
}

可以证明，while 循环最多执行两次（最开始执行一次使

n-m<d

，第二次就可兑换完）。

因此，此代码时间复杂度近似

O(1)

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

文章操作

暴力

正解

代码

相关推荐

评论

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