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

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

牛客对应题目链接:春游 (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,再来作比较。


目录
打赏
0
0
0
0
9
分享
相关文章
✨利用 SplittingJS 实现炫酷图片切换场景
✨利用 SplittingJS 实现炫酷图片切换场景
513 3
【数据挖掘】聚类趋势估计、簇数确定、质量测定等评估方法详解(图文解释 超详细)
【数据挖掘】聚类趋势估计、簇数确定、质量测定等评估方法详解(图文解释 超详细)
370 0
Linux系统之部署Linux管理面板1Panel
【10月更文挑战第20天】Linux系统之部署Linux管理面板1Panel
571 4
Linux系统之部署Linux管理面板1Panel
vue3 生命周期
【10月更文挑战第14天】vue3 生命周期
|
11月前
|
优化Maven镜像配置:使用阿里云加速依赖下载
更新Maven镜像配置至关重要,尤其使用阿里云仓库时。在`settings.xml`中加入特定镜像配置可显著提升依赖下载速度。示例配置指定了阿里云镜像ID、替代表态仓库、安全的URL、默认布局及启用版本管理。需定位至用户目录下的`.m2/`文件夹编辑`settings.xml`,添加镜像信息后保存测试。若下载仍慢,考虑网络状况或备选镜像。多镜像设置时需注意避免冲突。
1602 3
DataWorks操作报错合集之点击校验时出现报错,该如何解决
DataWorks是阿里云提供的一站式大数据开发与治理平台,支持数据集成、数据开发、数据服务、数据质量管理、数据安全管理等全流程数据处理。在使用DataWorks过程中,可能会遇到各种操作报错。以下是一些常见的报错情况及其可能的原因和解决方法。
194 0
【PTA刷题】 顺序表(删除)(代码+详解)
【PTA刷题】 顺序表(删除)(代码+详解)
455 0
【Go语言专栏】Go语言的性能优化与内存分析
【4月更文挑战第30天】本文探讨了Go语言的性能优化策略和内存分析方法。性能优化原则包括基准测试、分析瓶颈、避免过早优化和持续监控。优化策略涉及减少内存分配、避免内存逃逸、利用并发、优化算法和数据结构以及减少系统调用。内存分析借助于Go的`pprof`工具、内存分配跟踪和第三方工具,以发现内存泄漏和管理问题。通过这些方法,开发者能提升Go程序效率和资源利用率。
169 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问