春游

题目链接:nowcoder 219035

到主站看:https://blog.csdn.net/weixin_43346722/article/details/116172499

题目大意

有 n 个人,然后有 a 元的 2 人船,有 b 元的三人船,船不一定要坐满。
问你让所有人都有船做的最小价格。

思路

我们先看到只有 2 人船 3 人船,那如果每有 6 个人,我们就可以比较一下是买 3 个 a 元的 2 船或者买 2 个 b 元的三人船,看哪种便宜。

然后每 6 个人都这么买,最后就只剩不到 6 个人还没有座位。
那只有 6 个人,我们完全可以直接暴力枚举两种船的个数,在所有人都能做进去的情况里面选费用最小的就好了。

代码

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

int T;
ll n, a, b, ans, minn;

int main() {
    scanf("%d", &T);
    while (T--) {
        minn = 1e18;

        scanf("%lld %lld %lld", &n, &a, &b);
        if (n > 6) {//直接处理 6 个人的
            n -= 6;
            ans = (n / 6) * min(a * 3, b * 2);
            n %= 6;
            n += 6; 
        }

        for (int i = 0; i <= 10; i++)//剩下的 <=6 个人直接暴力处理
            for (int j = 0; j <= 10; j++)
                if (i * 2 + j * 3 >= n)
                    minn = min(minn, i * a + j * b);

        printf("%lld\n", ans + minn);
    }

    return 0;
}