每日OJ题_牛客_春游_贪心+数学_C++_Java

目录

牛客_春游_贪心+数学

题目解析

C++代码

Java代码

---

牛客_春游_贪心+数学

春游

描述：

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

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

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

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

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

输入描述：

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

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

输出描述：

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

---

题目解析

        优先选性价比最高的，然后小部分改动。考虑如果先选2更优，那么最多可能选1个3，因为2和3的最小公倍数是6，如果选了2个3不如选3个2。再考虑先选3更优，那么可能会选择1个2或者2个2，如果选择3个2不如选择2个3更优。所以从这5种情况里找最优解就好了。

C++代码

#include <iostream>
using namespace std;
#define int long longint t;
int n, a, b;int fun()
{if(n <= 2)return min(a, b);int 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;
}signed main()
{cin >> t;while(t--){cin >> n >> a >> b;cout << fun() << endl;}return 0;
}

Java代码

import java.util.*;
public class Main
{public static void main(String[] s){Scanner in = new Scanner(System.in);int t = in.nextInt();while(t-- != 0){long n = in.nextLong(), a = in.nextLong(), b = in.nextLong();long ret = 0;if(n <= 2) // 边界情况{ret = Math.min(a, b);}else{if(a * 3 < b * 2) // 尽可能的选择双⼈船{ret += n / 2 * a;n %= 2;if(n == 1){ret += Math.min(Math.min(a, b), b - a);}}else // 尽可能的选择三⼈船{ret += n / 3 * b;n %= 3;if(n == 1)ret += Math.min(Math.min(a, b), 2 * a - b);if(n == 2)ret += Math.min(Math.min(a, b), 3 * a - b);}}System.out.println(ret);}}
}