【c++笔试强训】（第十六篇）
目录
游游的⽔果⼤礼包（枚举）
题目解析
讲解算法原理
编写代码
买卖股票的最好时机(⼆)（贪⼼）
题目解析
讲解算法原理
编写代码
游游的⽔果⼤礼包（枚举）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
题目描述
游游有nnn个苹果，mmm个桃子。她可以把2个苹果和1个桃子组成价值aaa元的一号水果大礼包，也可以把1个苹果和2个桃子组成价值bbb元的二号水果大礼包。游游想知道，自己最多能组成多少价值总和的大礼包？
输入描述:
四个正整数n,m,a,bn,m,a,bn,m,a,b，用空格隔开。分别代表苹果的数量、桃子的数量、一号大礼包价值、二号大礼包价值。
1≤n,m,a,b≤1061\leq n,m,a,b\leq 10^61≤n,m,a,b≤106输出描述:
一个整数，代表大礼包的最大价值总和。
示例1
输入
3 4 1 2
3 4 1 2
输出
4
4
说明
组成两个二号水果大礼包，使用了2个苹果和4个桃子。总价值为4。
示例2
输入
1 1 5 6
1 1 5 6
输出
0
0
讲解算法原理
解法：
算法思路：
很容易想到贪⼼，但是很不幸，贪⼼是错的。
正确的解法应该是枚举所有的情况~
编写代码
c++算法代码：
#include <iostream>
using namespace std;
long long n, m, a, b;
int main()
{
cin >> n >> m >> a >> b;
long long ret = 0;
for(long long x = 0; x <= min(n / 2, m); x++) // 枚举 1 号礼包的个数 {
long long y = min(n - x * 2, (m - x) / 2); // 计算 2 号礼包的个数 ret = max(ret, a * x + b * y); }
cout << ret << endl;
return 0;
}java算法代码：
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in); long n = in.nextInt(); long m = in.nextInt(); long a = in.nextInt(); long b = in.nextInt();
long ret = 0;
for(long x = 0; x <= Math.min(n / 2, m); x++) // 枚举 1 号礼包的个数 {
long y = Math.min(n - x * 2, (m - x) / 2); // 计算 2 号礼包的个数 ret = Math.max(ret, a * x + b * y); }
System.out.println(ret);
}
}
买卖股票的最好时机(⼆)（贪⼼）
题目解析
1.题目链接：买卖股票的最好时机(二)_牛客题霸_牛客网
2.题目描述
描述
假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费
数据范围： 0 \le n \le 1 \times 10^50≤n≤1×105 ， 1 \le prices[i] \le 10^41≤prices[i]≤104
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
输入描述：
第一行输入一个正整数 n ，表示数组 prices 的长度
第二行输入 n 个正整数，表示数组中prices的值
输出描述：
输出最大收益
示例1
输入：
7
8 9 2 5 4 7 1输出：
7
说明：
在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
总获利1+3+3=7，返回7
示例2
输入：
5
5 4 3 2 1输出：
0
说明：
由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。
示例3
输入：
5
1 2 3 4 5输出：
4
说明：
第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。
讲解算法原理
解法：
算法思路：
⼩贪⼼：
因为可以⽆限次交易，因此，只要股票的价格有上升，就统统把利润拿到⼿。
编写代码
c++算法代码：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int arr[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> arr[i];
int ret = 0;
for(int i = 1; i < n; i++) if(arr[i] > arr[i - 1]) ret += arr[i] - arr[i - 1];
cout << ret << endl;
return 0;
}java算法代码：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++)
{
arr[i] = in.nextInt();
}
int ret = 0;
for(int i = 1; i < n; i++)
{
if(arr[i] > arr[i - 1])
{
ret += arr[i] - arr[i - 1];
}
}
System.out.println(ret);
}
}