【C++笔试强训】如何成为算法糕手Day2

学习编程就得循环渐进，扎实基础，勿在浮沙筑高台

循环渐进Forward-CSDN博客

第一题：牛牛的快递

第二题：最小花费爬楼梯

第三题：数组中两个字符串的最小距离

补充0x3f3f3f3f

第一题：牛牛的快递

牛客网做题链接：牛牛的快递_牛客题霸_牛客网 (nowcoder.com)

思路：
读题可知总共有四种解决方式

(1)快递不加急且小于20kg;
(2)快递加急且小于20kg;
(3)快递不加急且大于20kg;
(4)快递加急且大于20kg;

#include <iostream>
using namespace std;int main()
{float a = 0;char b = 0;int count = 0;cin >> a >> b;if(a < 1 && b == 'n')cout << 20;else if(a < 1 && b == 'y')cout << 25;else if(a>=1 && b == 'n'){while(--a > 0){count++;}cout << 20 + count;}else if(a>=1 && b == 'y'){while(--a > 0){count++;}cout << 20 + count + 5;}return 0;
}

第二题：最小花费爬楼梯

牛客网做题链接：最小花费爬楼梯_牛客题霸_牛客网 (nowcoder.com)

这道题目是一个典型的动态规划问题。解决这类问题通常采用从后向前的思考方式。考虑到每次可以选择跳一级或者两级台阶，因此到达最后一个台阶的最小花费，取决于从倒数第二个台阶或倒数第三个台阶到达所需的最小花费。我们只需要计算这两种情况下的最小值，就可以得到到达最后一个台阶的总花费。按照这种逻辑，从后向前推算，每一级台阶的最小花费都可以通过这种方式得出。我们可以使用一个cost数组来存储到达每一级台阶的花费，同时使用一个dp数组来记录到达每一级台阶的最小总花费。

#include <iostream>
using namespace std;const int N = 1e5 + 10;int n;
int cost[N];
int dp[N];int main()
{cin >> n;for(int i = 0;i < n;i++){cin >> cost[i];}for(int i = 2; i <= n; i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}cout << dp[n] << endl;return 0;
}

第三题：数组中两个字符串的最小距离

牛客网做题链接：数组中两个字符串的最小距离__牛客网 (nowcoder.com)

初始化变量：
- pre1 和 pre2 初始化为 -1，表示尚未找到字符串1和字符串2。
- ret 初始化为一个非常大的数，用于记录两个字符串之间的最小距离。
遍历数组：
- 在一次遍历中，检查当前元素是否为字符串1或字符串2。
- 如果找到字符串1：
  - 如果 pre2 已经指向字符串2，计算当前 pre1 和 pre2 之间的距离，并更新 ret 为最小值。
  - 更新 pre1 为当前索引。
- 如果找到字符串2：
  - 如果 pre1 已经指向字符串1，计算当前 pre1 和 pre2 之间的距离，并更新 ret 为最小值。
  - 更新 pre2 为当前索引。
算法的正确性：
- 当 pre1 首次找到字符串1后，继续遍历直到 pre2 找到字符串2，此时计算的距离是最小的，因为后续的字符串2距离 pre1 都会更远。
- 如果在 pre1 和 pre2 之间还有更优的字符串1位置，那么在 pre2 找到字符串2之后，继续遍历会找到这个更优的位置，并更新最小距离。

这个贪心算法之所以有效，是因为它在每次找到字符串1或字符串2时，都会尝试计算并更新最小距离，而不是等到遍历结束后再计算。这种方法确保了每次更新都是基于当前找到的最优解，从而避免了不必要的重复计算，降低了时间复杂度。

#include <iostream>
#include <string>
#include <climits> // 用于 INT_MAX 
using namespace std;int main() {int n;string str1, str2;string strs;cin >> n;cin >> str1 >> str2;int prev1 = -1, prev2 = -1, ret = INT_MAX ;//0x3f3f3f3ffor (int i = 0; i < n; i++){cin >> strs;if (strs == str1){ // 去前⾯找最近的 str2if (prev2 != -1){ret = min(ret, i - prev2);}prev1 = i;} else if (strs == str2){ // 去前⾯找 str1if (prev1 != -1){ret = min(ret, i - prev1);}prev2 = i;}}if(ret == INT_MAX ) //说明str1和str2其中一个或两个不存在或为NUlL //0x3f3f3f3fcout << -1 << endl;else cout << ret << endl;return 0;
}

补充0x3f3f3f3f

有时候使用的 0x3f3f3f3f 是一个在编程中常见的技巧，尤其是在竞赛编程和算法实现中。这个值是一个十六进制数，转换为十进制后大约是 1061109567，这个值比 int 类型（通常是32位）能表示的最大值（INT_MAX，通常为 2147483647）要小，但足够大，可以用作一个初始的“无穷大”值，在后续的比较中被实际的最小值替换。