C/C++每日一练18

第一题：压缩字符串

题目描述：将字符串中连续重复的字符压缩为 “字符 + 次数” 的形式，若次数为 1 则只保留字符。例如输入 “aabcccccaaa”，输出 “a2b1c5a3”。算法原理：遍历字符串，用一个变量记录当前字符，另一个变量记录连续出现的次数。当遇到与当前字符不同的字符时，将当前字符和次数拼接到结果中，然后更新当前字符和次数。遍历结束后，别忘了拼接最后一组字符和次数。代码：

cpp

运行

#include <iostream> #include <string> using namespace std; int main() { string s, res; cin >> s; if (s.empty()) { cout << res << endl; return 0; } char curr = s[0]; int cnt = 1; for (int i = 1; i < s.size(); ++i) { if (s[i] == curr) { cnt++; } else { res += curr + to_string(cnt); curr = s[i]; cnt = 1; } } res += curr + to_string(cnt); cout << res << endl; return 0; }

第二题：恰卡和蜜柑

题目描述：恰卡有 n 个蜜柑，第 i 个蜜柑的甜度为 a [i]，他想选 k 个蜜柑，使得甜度之和最大，求最大甜度和。算法原理：这是典型的 “选最大 k 个数求和” 问题。可以先对数组进行降序排序，然后取前 k 个数相加即可。排序可以用 C++ 的 sort 函数，通过自定义比较器实现降序。代码：

cpp

运行

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } sort(a.rbegin(), a.rend()); int sum = 0; for (int i = 0; i < k; ++i) { sum += a[i]; } cout << sum << endl; return 0; }

第三题：01 背包

题目描述：有 n 件物品，每件物品有重量 w [i] 和价值 v [i]，背包容量为 C，每件物品只能选一次，求背包能装下的最大价值。算法原理：用动态规划解决。定义 dp [j] 为容量为 j 的背包能装的最大价值。初始时 dp [0]=0，其他 dp [j]=0。对于每件物品 i，从容量 C 倒序遍历到 w [i]，更新 dp [j] = max (dp [j], dp [j - w [i]] + v [i])。倒序遍历是为了保证每件物品只被选一次。最后 dp [C] 就是答案。代码：

cpp

运行

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, C; cin >> n >> C; vector<int> w(n), v(n); for (int i = 0; i < n; ++i) { cin >> w[i] >> v[i]; } vector<int> dp(C + 1, 0); for (int i = 0; i < n; ++i) { for (int j = C; j >= w[i]; --j) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[C] << endl; return 0; }