1.牛牛的快递题目描述牛牛寄快递收费规则重量≤1kg起步价20 元超过 1kg 部分每 kg 加 1 元不足 1kg 按 1kg 向上取整加急y额外 5 元不加急n不加价输入浮点数重量a字符by/n 输出总快递费用样例输入 11.5 y计算1.5 向上取整 2kg20(2-1)526 → 输出26输入 20.7 n不足 1kg不加急 → 输出20核心思路对重量向上取整ceil(a)基础费用20 (向上取整后的重量 - 1)判断加急y则总价 5代码实现C 版本ceil 库函数最简写法cpp运行#include iostream #include cmath // ceil向上取整 using namespace std; int main() { double w; char op; cin w op; int kg ceil(w); // 不足1kg也变成1 int cost 20 (kg - 1); if (op y) cost 5; cout cost; return 0; }不用 ceil 的手动向上取整思路不用库函数也能实现整数部分int_w (int)w小数部分frac w - int_w若frac 0实际重量int_w 1否则int_wcpp运行// 替换 kg ceil(w) 的代码 int int_w (int)w; int real_kg; if (w - int_w 0) real_kg int_w 1; else real_kg int_w;易错点提醒浮点数直接强转 int 是向下取整不能直接用0.1、0.9 这类小于 1 的数向上取整后都是 1只收 20 元输入字符前后有空格读取时不需要额外处理cin/input 会自动分隔。2.使用最小花费爬楼梯题目大意数组costcost[i]代表第i阶台阶的花费。 你可以从下标 0 或下标 1 出发 每次可以爬 1 或 2 个台阶 爬到楼顶数组末尾之后才算结束求最小总花费。示例cost [10,15,20]路径15 → 楼顶花费 15 输出15cost [1,100,1,1,1,100,1,1,100,1]输出6动态规划思路状态定义dp[i]到达第i级台阶的最小花费转移方程到达 i 只能从 i-1 或 i-2 过来\(dp[i] \min(dp[i-1], dp[i-2]) cost[i]\)初始条件plaintextdp[0] cost[0] dp[1] cost[1]答案楼顶在最后一阶后面所以取min(dp[n-1], dp[n-2])C 完整代码1. dp 数组标准版cpp运行#include iostream #include vector #include algorithm using namespace std; int minCostClimbingStairs(vectorint cost) { int n cost.size(); vectorint dp(n); dp[0] cost[0]; dp[1] cost[1]; for(int i 2; i n; i){ dp[i] min(dp[i-1], dp[i-2]) cost[i]; } return min(dp[n-1], dp[n-2]); } int main(){ vectorint c {1,100,1,1,1,100,1,1,100,1}; cout minCostClimbingStairs(c); return 0; }关键点总结起点可选 0 / 1因此初始化dp[0]、dp[1]每上一层必须支付该层费用终点是楼顶不用支付最后一层之后的费用取最后两阶最小值空间可优化到 O (1)不用开数组3.数组中两个字符串的最小距离题目描述给定一个字符串数组strs再给定两个字符串s1、s2求数组中两个字符串出现位置的最小下标差值。规则若s1 s2题目一般保证数组中分开多次出现求同个字符串两次出现的最小距离若数组不存在s1或不存在s2返回-1距离定义abs(i - j)求所有配对中最小的一个。示例输入[a,b,c,a,d,b]s1as2b a 出现下标0、3 b 出现下标1、5 配对距离|0-1|1|0-5|5|3-1|2|3-5|2 最小距离1最优思路一次遍历 O (n)空间 O (1)只用两个变量记录上一次遇到 s1、s2 的下标idx1最近一次 s1 的位置初始-1idx2最近一次 s2 的位置初始-1遍历数组每个下标 i当前元素 s1 → 更新 idx1 i当前元素 s2 → 更新 idx2 i如果 idx1 ! -1 且 idx2 ! -1计算距离更新全局最小值特殊分支s1 s2两个字符串相同不能用上面逻辑需要单独处理 只记录上一次出现的下标 pre再次遇到时计算i-pre更新最小值。#include iostream #include vector #include string #include climits #include cmath using namespace std; int minDistance(vectorstring strs, string s1, string s2) { if (s1 s2) { int minDis INT_MAX; int pre -1; for (int i 0; i strs.size(); i) { if (strs[i] s1) { if (pre ! -1) { minDis min(minDis, i - pre); } pre i; } } return minDis INT_MAX ? -1 : minDis; } int idx1 -1, idx2 -1; int minDis INT_MAX; for (int i 0; i strs.size(); i) { if (strs[i] s1) idx1 i; if (strs[i] s2) idx2 i; if (idx1 ! -1 idx2 ! -1) { minDis min(minDis, abs(idx1 - idx2)); } } return minDis INT_MAX ? -1 : minDis; } int main() { vectorstring arr {a,b,c,a,d,b}; cout minDistance(arr, a, b) endl; // 输出1 return 0; }复杂度分析时间O (N)仅遍历数组一次空间O (1)只用常数变量易错点忘记处理s1 s2场景会直接算错初始最小距离要设极大值最后判断是否更新过没更新说明缺字符串返回 - 1每次更新下标后立刻计算距离不用存储全部下标节省空间。谢谢