【C++】牛客——春游

✨题目链接：春游

✨题目描述

盼望着，盼望着，东风来了，春天脚步近了。

值此大好春光，老师组织了同学们出去划船，划船项目收费如下：

双人船最多坐两人，也可以坐一人，收费a元

三人船最多坐三人，也可以坐两人或者一人，收费b元

本次出游加上带队老师共n人，如何安排能使得花费最小呢？

✨输入描述:

第一行给出一个正整数 𝑇(1≤𝑇≤1000) ，代表测试数据的组数。

接下来 T 行每行给出三个正整数𝑛,𝑎,𝑏,1≤𝑛,𝑎,𝑏≤10^9 ，含义如题。

✨输出描述:

每组输入输出一行，代表最小的花费

✨示例1

📍输入

2
2 20 200
3 20 20

📍输出

20
20

✨解题思路

首先我们可以计算双人船和三人船中每个玩家的花费，我们要在尽可能的情况下选择单价少的船优先安排。

利用 一点小学数学知识思考一下：

如果$$3a\le 2b$$
说明我们要先尽可能安排双人船坐满，
如果恰n%2==0，那就不需要额外安排船，
如果剩下一个人，那么就考虑是给他新添一艘船或者拿掉一个a，和之前2个人一起去坐3人船。
如果$$3a>2b$$
说明我们要先尽可能安排三人船坐满，那么与上面类似，我们可能留下
0,1,2三种情况，然后比较取最值。

✨代码

#include <iostream>
using namespace std;
typedef long long ll;
int main() {
    ll t,n,a,b;
    cin>>t;
    while(t--)
    {
        ll ret=0;
        cin>>n>>a>>b;
        if (n <= 2) {
        cout<<min(a, b)<<endl;
        }
        else if(3*a<=2*b)//双人坐满
        {
            ret=n/2*a;
            if(n%2!=0)
            {
                //剩一个人
                //要么多坐一个a or b
                //要么和另外两个去掉一个a一起坐一个b
                ret=min(ret+min(a,b),ret-a+b);
            }
            cout<<ret<<endl;
        }
        else
        {
            //三人坐满
            ret=n/3*b;
            if(n%3==1)
            {
                //剩一个
                //多一个a  or  多一个b or 少一个b多2a
                ret=min(ret+min(a,b),ret-b+2*a);

            }
            else if(n%3==2)
            {
                //剩两个
                //多一个a or 多一个b or 少一个b多3a 
                ret=min(ret+min(a,b),ret-b+3*a);
                
            }
            cout<<ret<<endl;
        }
    }
    return 0;
}

※ 如果文章对你有帮助的话，可以点赞收藏！！谢谢支持