题目描述

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

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

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

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

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

样例

2
2 20 200
3 20 20

20
20

算法1

(枚举) $O(n)$

分类讨论问题,还是自己的弱项哎

C++ 代码

include<bits/stdc++.h>
using namespace std;
#define rd(x)   scanf("%lld",&x)
typedef long long ll;
int main()
{
    ll t;
    rd(t);
    while(t--)
    {
        ll n;
        ll res=1e18;
        rd(n);
        ll a,b;
        rd(a),rd(b);
        res=min(res,(n+1)/2*a);//全A
        if(n>=3)    res=min(res,(n+1-3)/2*a+b);//A+1b
        res=min(res,(n+2)/3*b);//全B
        if(n>=2)    res=min(res,(n+2-2)/3*b+a);//B+1a
        if(n>=4)    res=min(res,(n+2-4)/3*b+2*a);//B+2a
        cout<<res<<endl;
    }
}