从“班委竞选”到“广告投放”：聊聊CCPC真题里那些有趣的模拟与贪心思路
从“班委竞选”到“广告投放”：算法竞赛中的模拟与贪心思维实战
第一次参加算法竞赛时，我盯着屏幕上那道"班委竞选"的题目足足发了十分钟呆——明明看起来只是统计票数的小学生题目，提交后却总是Wrong Answer。直到比赛结束才发现，原来漏掉了候选人票数相同时的特殊处理。这种"看似简单实则暗藏玄机"的模拟题，和后来遇到的"广告投放"这类需要复杂贪心策略的题目，构成了算法竞赛中最具教学价值的对比案例。
1. 为什么模拟题总让人阴沟里翻船
去年CCPC省赛中有道题要求统计校园歌手大赛的评分，37%的参赛者在第一个测试点就栽了跟头。这类题目往往披着日常生活的外衣，却设置了精确的数据边界条件。以经典的"班委竞选"为例，题目描述是这样的：
某班级有n位同学参与班委竞选，每人投一票给m位候选人中的一位。若某候选人票数超过n/2，则直接当选；否则所有候选人进入第二轮投票。请编写程序确定选举结果。
常见翻车点分析：
- 边界条件：当n为奇数时，n/2应该向下取整还是向上取整？
- 特殊情况：所有候选人票数相同如何处理？
- 输入验证：是否考虑无效票（投票编号超出m范围）？
def election(votes, m): n = len(votes) counter = [0] * (m + 1) # 候选人编号1~m for v in votes: if 1 <= v <= m: counter[v] += 1 max_vote = max(counter[1:]) if max_vote > n // 2: # 注意这里是整数除法 return counter.index(max_vote) else: return -1 # 表示进入第二轮实际比赛中更隐蔽的陷阱：题目可能要求当平票时返回票数最高的候选人中最小编号，这时max()函数就不够用了，需要手动实现查找逻辑。这就是为什么建议即使面对简单题目，也要至少设计3组测试用例：
- 常规情况（有明显胜者）
- 边界情况（正好半数）
- 极端情况（全员弃权或全部投给无效候选人）
2. 广告投放中的贪心策略演化
当问题从"班委竞选"变成"广告投放"，复杂度立刻提升了一个数量级。来看这道经典变种题：
某视频平台有N个广告位，M个广告主，第i个广告主出价b_i希望获得a_i次展示。平台需要选择一组广告主使得总展示次数不超过N的前提下收益最大。
2.1 从暴力枚举到贪心优化
最直观的解法是枚举所有可能的广告主组合，时间复杂度O(2^M)。当M>20时就不可行了。这时我们需要观察问题是否具有贪心选择性质：
# 按单价排序的贪心解法 ads = sorted([(b_i/a_i, a_i, b_i) for (a_i,b_i) in zip(a,b)], reverse=True) total = 0 profit = 0 for _, a_i, b_i in ads: if total + a_i <= N: total += a_i profit += b_i else: remain = N - total profit += remain * (b_i / a_i) break但这样真的对吗？其实这里暗藏两个认知误区：
- 单价陷阱：单纯按b_i/a_i排序可能错过组合效益
- 离散问题：广告展示次数必须是整数，不能简单按比例分配
2.2 动态规划与贪心的边界
当意识到这是经典的0-1背包问题变种时，我们可以采用动态规划：
dp = [0] * (N + 1) for i in range(M): for j in range(N, a[i] - 1, -1): dp[j] = max(dp[j], dp[j - a[i]] + b[i])但在实际竞赛中，当N很大时（比如1e9），这种O(MN)的解法又会超时。此时需要结合题目特点寻找特殊性质——如果所有a_i都是N的约数，或者b_i与a_i成线性关系，就可能存在更优的贪心策略。
3. 模拟与贪心的思维训练法
在杭州电子科技大学OJ的分类题库中，我将模拟题和贪心题交叉练习时发现一个有趣现象：模拟题的错误往往源于场景理解不完整，而贪心题的错误多来自性质证明不严谨。为此我总结了一套训练方法：
三日训练循环：
- Day1：解3道模拟题，重点练习：
- 边界条件枚举（使用checklist）
- 输入输出格式的特殊要求
- Day2：解2道贪心题，重点练习：
- 反例构造（尝试破坏自己的算法）
- 严格数学证明
- Day3：混合练习，记录每道题的思考时间分布
效果验证表：
| 训练阶段 | 模拟题AC率 | 贪心题AC率 | 平均思考时间 |
|---|---|---|---|
| 前测 | 65% | 42% | 25min |
| 第1周期 | 78% | 51% | 18min |
| 第2周期 | 89% | 63% | 12min |
4. 竞赛中的时间分配策略
去年带队参加CCPC时，我们的战术手册里有条铁律："30分钟法则"——如果一道题卡住超过30分钟，就必须切换。具体到不同题型：
模拟题：建议在15分钟内完成
- 前5分钟：仔细阅读+样例分析
- 中间5分钟：编写核心逻辑
- 最后5分钟：边界测试+调试
贪心/DP题：建议分阶段投入时间
- 前10分钟：暴力思路+小规模验证
- 接下来15分钟：优化策略设计
- 如果超时：保留当前解法作为保底，转战其他题目
关键提示：永远先写暴力解法，哪怕知道会超时。这不仅能拿到部分分数，更能帮助理解题目本质。
有次比赛我们就因为死磕一道"变形广告投放"题，导致最后来不及做简单的模拟题。后来复盘发现，如果先确保所有简单题AC，队伍排名能提升20位。这种策略性取舍，本身也是算法竞赛的重要能力。
在洛谷的题单系统中，我特别建了个"思维转换"专题，里面既有需要精密计算的模拟题，也有需要抽象建模的贪心题。每次练习时刻意打乱顺序，模拟真实比赛的题目分布。三个月后，团队在省赛中的读题准确率提高了40%，这就是刻意练习的力量。