打卡信奥刷题（3056）用C++实现信奥题 P6767 [BalticOI 2012/2020] 玫瑰 (Day0)-拓冰建站

P6767 [BalticOI 2012/2020] 玫瑰 (Day0)

题目背景

因为特殊原因，本题目另外24 2424组数据请在这里提交。

Valentine 是人赢。

题目描述

现在 Valentine 要给他的N NN个妹子买玫瑰花，现在 Valentine 面前有两家店，每一家店有无数朵玫瑰花，但是他们按束卖。第一家店一束花里有A AA朵，每一束花要用B BB块钱。第二家店一束花里有C CC朵，每一束花要用D DD块钱。

求 Valentine 至少买N NN朵花最少需要花多少钱。

至少可以这么理解，假如M > N M>NM>N，但是买M MM朵花的钱比买N NN朵花的少，Valentine 就会买M MM朵花，并把多出来的花给其他妹子，没错，Valentine 很花心。

输入格式

一行五个整数N , A , B , C , D N,A,B,C,DN,A,B,C,D，意义见题目所述。

输出格式

一行一个整数代表最小花费。

输入输出样例 #1

输入 #1

5 1 4 3 6

输出 #1

输入输出样例 #2

输入 #2

22 2 3 10 14

输出 #2

说明/提示

样例说明

对于样例1 11，Valentine 可以选择在第二家店买2 22束花。

对于样例2 22，Valentine 可以选择在第一家店买1 11束花，在第二家店买2 22束花。

数据规模与约定

本题采用捆绑测试。

Subtask 1（20 pts）：N , A , B , C , D ≤ 1000 N,A,B,C,D \le 1000N,A,B,C,D≤1000。
Subtask 2（80 pts）：无特殊限制。

对于100 % 100\%100%的数据，1 ≤ N ≤ 10 15 1 \le N \le 10^{15}1≤N≤1015，1 ≤ A , B , C , D ≤ 10 5 1 \le A,B,C,D \le 10^51≤A,B,C,D≤105，保证答案不超过10 18 10^{18}1018。

说明

翻译自 BalticOI 2020 Day0 B Roses。

与 BalticOI 2012 Day0 A 内容一致。

C++实现

#include<bits/stdc++.h>#defineRregister#definegc()getchar()#definelllonglong#defineldlongdoubleusingnamespacestd;inlinellrd(){R ll x=0;Rcharc=gc();while(c>'9'||c<'0')c=gc();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc();returnx;}// 快读加速intmain(){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);return0;}