题解 P6767 【[BalticOI 2020/2012 Day0] Roses】

sysong · 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