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