【c++笔试强训】（第四十五篇）
目录
⼩红的⼝罩（贪⼼+堆）
题目解析
讲解算法原理
编写代码
春游（模拟-分情况讨论）
题目解析
讲解算法原理
编写代码
⼩红的⼝罩（贪⼼+堆）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
题目描述
疫情来了，小红网购了 nnn 个口罩。
众所周知，戴口罩是很不舒服的。小红每个口罩戴一天的初始不舒适度为 aia_iai。
小红有时候会将口罩重复使用（注：这是非常不卫生的！），每次重复使用时，该口罩的不舒适度会翻倍！
小红想知道，自己在不舒适度总和不超过 kkk 的情况下，最多能用现有的口罩度过多少天？输入描述:
第一行输入两个正整数 nnn 和 kkk ，分别代表口罩的总数、以及小红最多能忍受的不舒适度总和。
第二行输入 nnn 个正整数 aia_iai ，用空格隔开。分别代表每个口罩初始的不舒适度。
1≤n≤105,1≤ai,k≤1091\leq n \leq 10^5, 1 \leq a_i,k \leq10^91≤n≤105,1≤ai,k≤109输出描述:
一个整数，代表小红最多能度过的天数。
示例1
输入
2 30 2 3
2 30
2 3输出
5
5
示例2
输入
3 5
7 6 8输出
0
讲解算法原理
解法：
算法思路：
⼩贪⼼+堆，没难度~
编写代码
c++算法代码：
#include <iostream>
#include <queue>
using namespace std;
int n, k;
int main()
{
cin >> n >> k;
priority_queue<int, vector<int>, greater<int>> heap; for(int i = 0; i < n; i++)
{
int x;
cin >> x;
heap.push(x);
}
int sum = 0, count = 0; while(true)
{
int t = heap.top(); heap.pop(); sum += t; heap.push(t * 2); count++; if(sum > k)
{
cout << count - 1 << endl; break;
}
}
return 0;
}java算法代码：
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in); int n = in.nextInt(), k = in.nextInt();
PriorityQueue<Integer> heap = new PriorityQueue<>(); for(int i = 0; i < n; i++)
{
int x = in.nextInt(); heap.add(x);
}
int sum = 0, count = 0; while(true)
{
int t = heap.poll(); sum += t; count++; heap.add(t * 2); if(sum > k)
{
System.out.println(count - 1); break;
}
}
}
}春游（模拟-分情况讨论）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
盼望着，盼望着，东风来了，春天脚步近了。
值此大好春光，老师组织了同学们出去划船，划船项目收费如下：
双人船最多坐两人，也可以坐一人，收费a{a}a元
三人船最多坐三人，也可以坐两人或者一人，收费b{b}b元
本次出游加上带队老师共n{n}n人，如何安排能使得花费最小呢？
输入描述:
第一行给出一个正整数 T(1≤T≤1000)T(1 \le T \le 1000)T(1≤T≤1000)，代表测试数据的组数。
接下来 T{T}T 行每行给出三个正整数n,a,b,1≤n,a,b≤109n, a, b,1 \le n,a,b \le 10^9n,a,b,1≤n,a,b≤109，含义如题。
输出描述:
每组输入输出一行，代表最小的花费
示例1
输入
2 2 20 200 3 20 20
2
2 20 200
3 20 20输出
20 20
20
20
讲解算法原理
解法：
算法思路：
贪⼼+分情况讨论。
编写代码
c++算法代码：
#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;
}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);
}
}
}