洛谷P6767 Roses

题目背景

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

Valentine 是人赢。

题目描述

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

5 1 4 3 6

输出 #1复制

12

输入 #2复制

22 2 3 10 14

输出 #2复制

31

说明/提示

样例说明

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

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

数据规模与约定

本题采用捆绑测试。

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

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

说明

翻译自 BalticOI 2020 Day0 B Roses。

与 BalticOI 2012 Day0 A 内容一致。

上代码：

#include "cstdio"
#include "algorithm"
#include "iostream"
long long n, a1, a2, b1, b2, ans, go;
int main() {
    std::cin >> n >> a1 >> b1 >> a2 >> b2;
    long double x = b1 * 1.0 / a1, y = b2 * 1.0 / a2;
    if (x < y)
        std::swap(a1, a2), std::swap(b1, b2);//为了方便之后的枚举
    ans = (n + a2 - 1) / a2 * b2;
    go = a2 / std::__gcd(a1, a2);
    for (long long i = go; i >= 0; i--) {
        long long t = i * b1;
        if (n - i * a1 >= 0)
            t = t + (n - i * a1 + a2 - 1) / a2 * b2;
        ans = std::min(ans, t);
    }
    std::cout << ans;
    return 0;
}