当前位置：首页 > news >正文

【C++笔试强训】day02

news 来源：原创 2024/9/19 16:55:11

牛牛的快递

思路

起步价20，注意超出的费用要向上取整，最后再根据是否加急外付5元。

代码

#include <iostream>
#include <cmath>
using namespace std;int main()
{double a;char b;int sum = 20;cin >> a >> b;if (a > 1) sum += ceil(a - 1);if (b == 'y') sum += 5;cout << sum << endl;return 0;
}

最小花费爬楼梯

DFS

爬楼梯问题是一个典型的具有重叠子问题的模型，自上而下地思考，将大问题转化为规模更小的子问题，对于任意第i阶，它可能是从i-1爬上来的，也可能是从i-2爬上来的，由于本题是要求总的最低花费，所以选择花费最小的那个。

边界：

i=0：只能爬一阶，花费是cost[0]。
i=1：同上，花费是cost[1]。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;int cost[N];
int n;int main()
{cin >> n;for (int i = 0; i < n; i++) cin >> cost[i];vector<int> memo(n + 1, -1);function <int(int)> dfs = [&](int i) -> int{if (i == 0) return cost[0];if (i == 1) return cost[1];if (memo[i] != -1) return memo[i];return memo[i] = cost[i] + min(dfs(i - 1), dfs(i - 2));};cout << min(dfs(n - 1), dfs(n - 2));return 0;
}

时间复杂度： $O (n)$ 。

动态规划

将记忆化搜索翻译成递推。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;int cost[N];
int n;int main()
{cin >> n;for (int i = 0; i < n; i++) cin >> cost[i];vector<int> dp(n);dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < n; i++)dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);cout << min(dp[n - 1], dp[n - 2]);return 0;
}

时间复杂度： $O (n)$ 。

数组中两个字符串的最小距离

思路

用数组统计并保存str1和str2在strs中出现的下标x和y。然后枚举所有可能的x和y的组合，得到一个最小差值。

代码

#include <bits/stdc++.h>
#include <vector>
using namespace std;const int N = 100010;
vector<int> pos[2];
string strs[N];
int len = INT_MAX;int main()
{int n;string s, t;cin >> n;cin >> s >> t;for (int i = 0; i < n; i++) {cin >> strs[i];if (strs[i] == s) pos[0].push_back(i);if (strs[i] == t) pos[1].push_back(i);}for (auto &x : pos[0])for (auto &y : pos[1])len = min(len, abs(x - y));if (len == INT_MAX) cout << -1 <<endl;else cout << len << endl;return 0;
}

时间复杂度： $O(n^2)$ 。
空间复杂度： $O (n)$ 。

优化

min_len 用于存储最小距离，初始化为 INT_MAX。
last_s 和 last_t 分别用于记录上一次出现字符串 s 和 t 的索引，初始化为 -1。

遍历字符串数组：

对于每个字符串，如果它等于 s，更新 last_s，并计算与 last_t 之间的距离，更新 min_len。
如果它等于 t，更新 last_t，并计算与 last_s 之间的距离，更新 min_len。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
string strs[N];int main()
{int n;string s, t;cin >> n;cin >> s >> t;for (int i = 0; i < n; i++) cin >> strs[i];int len = INT_MAX;int last_s = -1, last_t = -1;for (int i = 0; i < n; i++){if (strs[i] == s){last_s = i;if (last_t != -1) len = min(len, abs(last_s - last_t));}if (strs[i] == t){last_t = i;if (last_s != -1) len = min(len, abs(last_s - last_t));}}if (len == INT_MAX) cout << -1 << endl;else cout << len << endl;return 0;
}