【错题集-编程题】春游(模拟 - 分情况讨论)

简介: 【错题集-编程题】春游(模拟 - 分情况讨论)

牛客对应题目链接:春游 (nowcoder.com)


一、分析题目

贪心 + 分情况讨论。

首先可以计算双人船和三人船中每个同学需要花费的费用,要在尽可能的情况下选择单价少的船优先安排。

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

二、代码

//值得学习的代码
#include <iostream>
 
using namespace std;
typedef long long LL;
 
LL t;
LL n, a, b;
 
LL fun()
{
    // 边界情况
    if(n <= 2) return min(a, b);
    LL ret = 0;
    if(a * 3 < b * 2) // 尽可能的选择双⼈船
    {
        ret += n / 2 * a;
        n %= 2;
        if(n) ret += min(min(a, b), b - a);
    }
    else // 尽可能的选择三⼈船
    {
        ret += n / 3 * b;
        n %= 3;
        if(n == 1) ret += min(min(a, b), 2 * a - b);
        if(n == 2) ret += min(min(a, b), 3 * a - b);
    }
    return ret;
}
 
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n >> a >> b;
        cout << fun() << endl;
    }
 
    return 0;
}

三、反思与改进

这题纯模拟,我是从人数的角度出发的,其实应该从选择的角度出发。其实可以从 a/2 : b/3 转化为 3a : 2b,再来作比较。


相关文章
【期末不挂科-单片机考前速过系列P6】(第六章:10题速过定时计数器的结构和工作方式例题)经典例题盘点(带图解析)
【期末不挂科-单片机考前速过系列P6】(第六章:10题速过定时计数器的结构和工作方式例题)经典例题盘点(带图解析)
|
2天前
1047 编程团体赛 (20 分)
1047 编程团体赛 (20 分)
|
1月前
|
小程序 JavaScript Java
基于Java的大学生心理健康答题小程序设计与实现(亮点:选题新颖、可以发布试卷设置题目、自动判卷、上传答案、答案解析)
基于Java的大学生心理健康答题小程序设计与实现(亮点:选题新颖、可以发布试卷设置题目、自动判卷、上传答案、答案解析)
61 0
|
1月前
|
自然语言处理 监控 数据可视化
第七章项目范围管理(选择4分,偶尔考案例)
第七章项目范围管理(选择4分,偶尔考案例)
|
1月前
|
自然语言处理 监控 项目管理
第六章项目整体管理(选择5分,案例偶尔考)
第六章项目整体管理(选择5分,案例偶尔考)
离散数学笔记_第一章:逻辑和证明(1)(上)
离散数学笔记_第一章:逻辑和证明(1)(上)
82 0
离散数学笔记_第一章:逻辑和证明(1)(下)
离散数学笔记_第一章:逻辑和证明(1)(下)
82 0
离散数学笔记_第一章:逻辑和证明(3)
离散数学笔记_第一章:逻辑和证明(3)
138 0
|
自然语言处理 索引
离散数学笔记_第一章:逻辑和证明(2 )
离散数学笔记_第一章:逻辑和证明(2 )
101 0
数学知识补充(一)度量空间
数学知识补充(一)度量空间
59 0

热门文章

最新文章