【C++题解】贪心和模拟

4小时编码练习计划，专注于贪心算法和复杂模拟题，旨在锻炼您的算法思维、代码实现能力和耐心。

下午 (4小时): 贪心思维与代码实现力

今天的重点是两种在算法竞赛和工程中都至关重要的能力：贪心选择和复杂逻辑的精确实现。贪心算法考察的是能否洞察问题的本质，做出局部最优决策；而复杂模拟题则考验代码的组织能力、细节处理和调试耐心，这同样是CCF认证考试中的高频考点。

练习计划概览

• 总时长: 约 4 小时

• 核心目标:

  1. 理解贪心算法的本质：在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致全局结果最好或最优。

  2. 学习并实践经典的贪心模型，如区间调度问题。

  3. 挑战一道需求复杂、规则繁多的CCF真题，锻炼将大段文字描述转化为精确代码逻辑的能力。

  4. 提升代码调试能力和处理繁杂逻辑时的耐心与细致度。

第一部分：贪心算法——洞察局部最优解 (约 1.5 小时)

贪心算法的核心在于“贪”。它不从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优解。关键在于，你需要判断并证明这种局部最优选择能否导向全局最优。

题解

//P1803-先处理数据，然后贪心计算。#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main(){int n;cin >> n;int now = 0;int cnt = 0;vector<pair<int,int>> v;    while(n--){int start,end;cin >> start >> end;v.push_back(make_pair(start,end));}sort(v.begin(),v.end(),[](auto a,auto b){return a.second < b.second;});for(auto p : v){if(p.first>=now){now = p.second;cnt++;}}cout << cnt;return 0;
}

//29-2 使用二分限定范围，然后用贪心判断这个各个情况下的可行性和结果#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, k;cin >> n >> m >> k;vector<pair<int, int>> areas(n); // {time, cost}for(int i = 0; i < n; i++){cin >> areas[i].first >> areas[i].second; // time, cost}// 二分查找最优答案int left = k, right = 0;for(int i = 0; i < n; i++){right = max(right, areas[i].first);}while(left < right){int mid = (left + right) / 2;long long need = 0;// 计算达到mid天数需要的总资源for(int i = 0; i < n; i++){if(areas[i].first > mid){need += (long long)(areas[i].first - mid) * areas[i].second;}}if(need <= m){right = mid;} else {left = mid + 1;}}cout << left << endl;return 0;
}

练习建议:

• P1803: 解决此题的关键在于想清楚应该按什么标准进行排序。按开始时间？按区间长度？还是按结束时间？尝试思考不同排序策略的优劣，并理解为什么“按结束时间升序排序”是正确的贪心策略。

• CCF202303-2: 这类问题直接贪心不好做，但可以思考：如果我猜最终答案是 T 天，我能否用现有的 m 个资源实现这个目标？这个“能否实现”的子问题就可以用贪心来快速判断。这是一种非常重要的思想。

第二部分：复杂模拟——代码实现的试金石 (约 2 小时)

这类题目通常没有复杂的算法，但规则繁多、细节量大，极其考验代码的组织能力、细心程度和调试能力。在CCF认证中，这类题目通常是区分选手代码硬实力的关键。

（请从以下两题中精选一题进行攻克）

题解

//30-3 重难点就在理解那三四版的内容，然后转化成代码，注意边界处理，实则主要是耗时和注意力。#include <iostream>
#include <cstdio>
#include <string>using namespace std;
typedef long long LL;
const int N = 5e6 + 10;char str[N], ret[N];
int s, cnt, i;int tran(string str, int t) { // t进制转十进制int ret = 0;for (int i = 0; i < str.size(); i++) {if (isdigit(str[i])) ret = ret * t + str[i] - '0';else ret = ret * t + str[i] - 'a' + 10;}return ret;
}string twostr(char c1, char c2) { // 16进制转2进制string ret = "00000000";int a = isdigit(c1) ? c1 - '0' : c1 - 'a' + 10, b = isdigit(c2) ? c2 - '0' : c2 - 'a' + 10; // 改为数字for (int i = 3; i >= 0 && a; i--) { // 前四位ret[i] = a % 2 + '0';a /= 2;}for (int i = 7; i >= 4 && b; i--) { // 后四位ret[i] = b % 2 + '0';b /= 2;}return ret;
}int main() {cin >> s;for (int i = 0; i < (s - 1) / 8 + 1; i++) scanf("%s", str + i * 16);for (i = 0; i < s * 2; i += 2) { // 引导域string ss; ss += str[i]; ss += str[i + 1];if (tran(ss, 16) < 128) break; // 最高位为0，退出}for (i += 2; i < s * 2; i += 2) {string ss = twostr(str[i], str[i + 1]);if (ss[6] == '0' && ss[7] == '0') { // 字面量int le = tran(ss.substr(0, 6), 2), p, ct; // 获取字面量长度-1的值if (le >= 60) { // le+1>=61int dx = le - 59; // 存储字面量长度的字节数string lee;for (p = i + dx * 2; p > i; p -= 2) { // 小端序拼接lee += str[p]; lee += str[p + 1];}le = tran(lee, 16); // 获取字面量长度-1的值i += dx * 2;}for (p = i + 2, ct = 0; ct < le + 1; p += 2, ct++) { // 存储字面量字节ret[cnt++] = str[p];ret[cnt++] = str[p + 1];}i = p - 2;}else { // 回溯引用int l, o;if (ss[6] == '0' && ss[7] == '1') { // 01形式l = tran(ss.substr(3, 3), 2) + 4;ss = ss.substr(0, 3); ss += twostr(str[i + 2], str[i + 3]);i += 2;o = tran(ss, 2);}else { // 10形式l = tran(ss.substr(0, 6), 2) + 1;ss.clear(); ss += str[i + 4]; ss += str[i + 5]; ss += str[i + 2]; ss += str[i + 3];i += 4;o = tran(ss, 16);}int pcnt = cnt / 2; // 存一下现在的字节数for (int p = 2 * (pcnt - o), ct = 0; ct < l; p += 2, ct++) { // 从第pcnt-o个字节开始，输出l个字节if (o < l && p == 2 * pcnt) p = 2 * (pcnt - o); // 如果o<l，且到了末尾，回到起点，反复输出ret[cnt++] = ret[p];ret[cnt++] = ret[p + 1];}}}for (int i = 0; i < cnt; i++) {if (i && i % 16 == 0) cout << endl;cout << ret[i];}return 0;
}

练习建议:

• 先规划再动手: 在写代码之前，花15-20分钟仔细阅读题目，用纸笔把所有规则、分支和状态转移想清楚。可以为不同的功能模块设计独立的函数（如“解析一个元素”、“处理一次查询”），让主逻辑更清晰。

• 分步验证: 不要试图一次性写完所有代码。可以先实现最核心、最简单的部分（例如，只处理一种类型的元素或一种查询），验证无误后，再逐步添加其他复杂情况。

• 利用样例: 充分利用题目给出的样例，一步步手动模拟程序执行过程，对比自己的输出和预期输出，可以帮助快速定位逻辑错误。

目标达成自查 (约 0.5 小时)

完成以上练习后，进行复盘和总结：

1. 关于贪心算法:

   • 我解决贪心问题的一般思路是什么？（例如：排序 -> 循环 -> 按规则选择）

   • 垦田计划 这道题，为什么不能直接贪心，而要结合二分？（因为贪心的“性价比”会随着目标天数的改变而改变，没有一个固定的贪心标准）

2. 关于复杂模拟:

   • 在处理 解压缩 或 LDAP 时，我遇到了哪些困难？（例如：边界条件、状态管理、字符串处理的细节）

   • 我是如何组织我的代码来避免逻辑混乱的？（例如：使用结构体、类、辅助函数）

   • 如果再做一次，哪些地方可以改进，从而更快更准确地完成编码？