《从入门到精通：蓝桥杯编程大赛知识点全攻略》（十五）-股票买卖、货仓选址、等差数列、鸣人的影分身

前言

在这篇博客中，我们将深入探讨几种经典的算法问题，并提供相应的求解方法。我们将首先学习如何通过贪心算法来解决股票买卖和货仓选址问题。接着，我们会通过最大公约数来探讨等差数列的求解方法。最后，我们会利用动态规划来解决一个有趣的计算问题——鸣人影分身的能量分配。每个问题都结合了实际应用场景，并通过精妙的算法技巧来实现高效解法。

股票买卖

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入格式
第一行包含整数 N，表示数组长度。
第二行包含 N 个不大于 10000 的正整数，表示完整的数组。
输出格式
输出一个整数，表示最大利润。
数据范围
1≤N≤10⁵
输入样例1：

java">6
7 1 5 3 6 4

输出样例1：

java">7

输入样例2：

java">5
1 2 3 4 5

输出样例2：

java">4

输入样例3：

java">5
7 6 4 3 1

输出样例3：

java">0

样例解释
样例1：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例2：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 0。

算法思路

我们希望通过多次买卖来最大化利润。在每一笔交易中，我们希望通过买低卖高来获得利润。
具体来说：

连续增长的利润：每次只要当前价格比前一天的价格高，我们就进行一次交易（即买入昨天的股票，卖出今天的股票），赚取利润。
避免亏损：如果当前价格低于前一天的价格，则不进行交易，继续等待更高的价格。

从第 1 天开始，逐步遍历整个价格数组。
当当天价格高于前一天的价格时，计算并累加利润。
如果当天价格低于前一天的价格，则跳过。
最后累加的所有利润即为最大利润。

代码如下

java">package AcWingLanQiao;import java.io.*;public class 股票买卖 {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 100010;static int[] arr = new int[N];public static void main(String[] args)throws Exception {int n = nextInt();for (int i = 1; i <= n; i++) {arr[i] = nextInt();}int res = 0;for (int i = 1; i < n; i++) {if(arr[i] < arr[i+1]){res += arr[i+1] - arr[i];}}pw.println(res);pw.flush();}public static int nextInt()throws Exception{st.nextToken();return (int)st.nval;}}

货仓选址

在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数 N。
第二行 N 个整数 A1∼AN。
输出格式
输出一个整数，表示距离之和的最小值。
数据范围
1≤N≤100000,
0≤Ai≤40000
输入样例：

java">4
6 2 9 1

输出样例：

java">12

算法思路

在这里插入图片描述

中位数的性质：

如果我们将货仓建在数轴上某个位置，那么最小化所有商店距离之和的最优位置是所有商店位置的中位数。
为什么是中位数？因为中位数能够使得左侧的商店数量等于或尽量接近右侧商店的数量，减少总距离。
- 如果货仓在中位数的左边，移动货仓会增加距离；
- 如果货仓在中位数的右边，移动货仓也会增加距离。
- 所以，选择中位数可以保证总距离最小。

求解过程：

将商店的位置数组进行排序。
如果 N 是奇数，选择中位数作为货仓的位置。
如果 N 是偶数，选择任意一个中位数即可（理论上，这两者都会给出相同的最小总距离）。

计算最小距离之和：

一旦确定了货仓的位置（即中位数位置），遍历每个商店位置，计算距离并累加即可。

代码如下

java">import java.io.*;
import java.util.Arrays;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 100010;static int[] arr = new int[N];static int n;public static void main(String[] args)throws Exception {n = nextInt();for (int i = 0; i < n; i++) {arr[i] = nextInt();}Arrays.sort(arr,0,n);int res = 0;for (int i = 0; i < n; i++) {res += Math.abs(arr[i]- arr[n / 2]);}pw.println(res);pw.flush();}public static int nextInt()throws Exception{st.nextToken();return (int)st.nval;}
}

等差数列

数学老师给小明出了一道等差数列求和的题目。
但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1∼AN 并不一定是按等差数列中的顺序给出)
输出格式
输出一个整数表示答案。
数据范围
2≤N≤100000,
0≤Ai≤10⁹
输入样例：

java">5
2 6 4 10 20

输出样例：

java">10

样例解释
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。

算法思路

在这里插入图片描述
当然开始需要先了解辗转相除法求最大公约数，可以参考我这篇博客（试除法求约数+辗转相除法求最大公约数-java）
排序：

对给定的 N 个整数进行排序，确保能够顺利计算等差数列。

求最大公约数 (gcd)：

从排序后的数列中，计算第一个元素和其他元素的差值的最大公约数。通过 gcd 函数来求解。

项数：

如果 gcd 为 0，说明数列中所有元素相同，最短等差数列包含的项数就是 N。
否则，通过最大值、最小值与 GCD 计算最短等差数列的项数，即：

$项数 = （最大值 - 最小值） / d + 1$

代码如下

java">import java.io.*;
import java.util.Arrays;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 100010;static int[] arr = new int[N];static int n;public static void main(String[] args) throws Exception{n = nextInt();for (int i = 0; i < n; i++) {arr[i] = nextInt();}Arrays.sort(arr,0,n);int d = 0;for (int i = 0; i < n; i++) {d = gcd(d,arr[i] - arr[0]);}if(d == 0){pw.println(n);}else {pw.println((arr[n-1] - arr[0]) / d + 1);}pw.flush();}public static int gcd(int a,int b){if(b == 0) return a;return gcd(b,a%b);}public static int nextInt()throws Exception{st.nextToken();return (int)st.nval;}
}

鸣人的影分身

在火影忍者的世界里，令敌人捉摸不透是非常关键的。
我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为 M，他影分身的个数最多为 N，那么制造影分身时有多少种不同的分配方法？
注意：

影分身可以分配0点能量。
分配方案不考虑顺序，例如：M=7,N=3，那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。

输入格式
第一行是测试数据的数目 t。
以下每行均包含二个整数 M 和 N，以空格分开。
输出格式
对输入的每组数据 M 和 N，用一行输出分配的方法数。
数据范围
0≤t≤20,
1≤M,N≤10
输入样例：

java">1
7 3

输出样例：

java">8

算法思路

在这里插入图片描述
设定一个二维数组 dp，其中 dp[i][j] 表示将 (i) 个能量点分配到 (j) 个影分身中的方法数。
以从两个状态来考虑：

影分身的最小能量值为0，问题就变成了将 (i) 个能量分配到 (j-1) 个影分身中，即 dp[i][j-1]。
影分身的最小能量值不为0，即给 (j) 个影分身分配至少每个1 点能量，问题就变成了将 (i-j) 个能量分配到 (j) 个影分身中，即 dp[i-j][j]。

因此最终的状态转移方程为dp[i][j] = dp[i][j-1] + dp[i - j][j]；
边界条件

dp[0][j] = 1：将 0 能量分配给 (n) 个影分身，只有一种方式，即每个影分身都分配 0 能量。
dp[i][0] = 0（对于 (m > 0)）：如果没有影分身，且能量大于 0，是不可能分配的。

dp[0][0] = 1；能量的枚举从0开始，个数的枚举从1开始，并且dp[i][j] = dp[i][j-1];
当能量大于等于个数时，dp[i][j] += dp[i-j][j];
最后查克拉能量为 m，他影分身的个数最多为 n，那么制造影分身时的方案数为dp[m][n]

代码如下

java">import java.io.*;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 11;public static void main(String[] args) throws Exception{int t = nextInt();while(t-->0){int m = nextInt();int n = nextInt();int[][] dp = new int[N][N];dp[0][0] = 1;for(int i = 0; i<= m; i++){for(int j = 1; j<= n; j++){dp[i][j] = dp[i][j-1];if(i >= j){dp[i][j] += dp[i-j][j];}}}pw.println(dp[m][n]);}pw.flush();}public static int nextInt()throws Exception {st.nextToken();return (int) st.nval;}
}