自动搬运

查看原文

来自洛谷，原作者为

	sysong AFO

搬运于2025-08-24 22:23:46，当前版本为作者最后更新于2020-10-03 16:36:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解 P6767 [BalticOI 2020/2012 Day0] Roses

用一种奇怪的姿势过了这题，还成了当时最优解，写一篇题解纪念一下。

题意

要买$N$朵花，每$A$朵$B$元，每$C$朵$D$元，问最少要花多少元。

思路

注意：开 $long\ long$ !

因为$N \le 10^{18}$

首先挑便宜的买，然而——会多买，所以考虑用另外一种替换掉多余部分。

所以，我们可以写出代码片段：

---

($ll$代替$long\ long$,$ld$代替$long\ double$)

ll n=rd(),a=rd(),b=rd(),c=rd(),d=rd(),ans=1e18;			// a,b,c,d 严格按照题目要求， ans 记录最小值

ld x=b*1.0/a,y=d*1.0/c;									// x,y 分别为 a,b 种花的单价

if(x>y)swap(a,c),swap(b,d);								// 如果 a 的单价贵，那么交换，保证 a 的单价低

ll s=(n+a-1)/a;											// 单价低的至少要买 s 束
														// 这里 +a-1 相当于 ceil 函数

for(R ll i=s,k;i>=0;i--)								// 总共有 s 种不过于浪费的买法
{
	k=i*b+max((ll)0,n-i*a+c-1)/c*d;						// i*b 表示 a 种的总价格，
    													// n-i*a 表示剩余需要花的朵数，同上求出总价格
	if(k<ans)ans=k;										// 打擂台选取最小值
}

printf("%lld\n",ans);

---

然后，我们就这样提交，然而——取得了TLE的好成绩，还有一个点过不了。

怎么办呢？

我们发现，当我们把多买的部分替换掉之后，$k$是会增加的（本来就挑便宜的买的嘛）

那是不是——

---

for(R ll i=s,k,f=1;i>=0&&f;i--)							// 在这里设置一个 flag f ，如果价格开始增加，
														// 那么就不用再循环下去了
{
	k=i*b+max((ll)0,n-i*a+c-1)/c*d;
	if(k<ans)ans=k;
	else f=0;											// 相当于 break; 
}

---

继续——WA

难道没有办法了吗？

还有什么问题？

我们再次发现（太难了）：

我们拿掉的部分加上新买的部分，可能还是会多买。

看来也许我们是冤枉他了

怎么解决呢？

我们看到上面那位dalao写了个$lcm$（最小公倍数）来限制循环次数，实际上不需要。

因为$A,C \le 10^{5}$！

我们最多只要循环$10^{5}$就足以计算可能最优的情况了！

（求$lcm$还要花时间，而且$A$,$C$的$lcm$还可能比$10^{5}$大）

那么就很简单了

$C++\ \ \ Code$

---

#include <bits/stdc++.h>
#define R register
#define gc() getchar()
#define ll long long
#define ld long double
using namespace std;

inline ll rd(){
	R ll x=0;R char c=gc();
	while(c>'9'||c<'0')c=gc();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc();
	return x;
}																// 快读加速

int main(){
	ll n=rd(),a=rd(),b=rd(),c=rd(),d=rd(),ans=1e18;
	ld x=b*1.0/a,y=d*1.0/c;
	if(x>y)swap(a,c),swap(b,d);
	ll s=(n+a-1)/a;
	for(R ll i=s,k,f=100000;i>=0&&f;i--,f--)					// 用 f 来限制循环次数
		{
			k=i*b+max((ll)0,n-i*a+c-1)/c*d;
			if(k<ans)ans=k;
		}
	printf("%lld\n",ans);
	return 0;
}

---

终于$AC$了！（另外$24$组数据也已过）

---

码字不易，望通过！

by jsntsys

$2020.10.3$