从买票看算法：用‘折半搜索’解决洛谷P4799冰球赛购票难题（附C++代码）

从买票看算法：用‘折半搜索’解决洛谷P4799冰球赛购票难题（附C++代码）

想象你正站在冰球赛售票处，手握有限的预算，面对40场不同价格的比赛门票。如何快速计算出所有可能的观赛组合？这个看似生活化的问题，背后隐藏着一个经典的算法优化难题——当暴力枚举的复杂度达到2^40量级时，我们需要更聪明的搜索策略。

折半搜索（Meet in the Middle）正是解决这类问题的利器。它像一位经验丰富的战术指挥官，将庞大的搜索任务拆分为两个并行的子任务，最后通过巧妙的合并策略得到最终解。本文将带你从实际问题出发，深入理解这一算法的精妙之处，并掌握如何用C++高效实现。

1. 问题本质与暴力解法局限

洛谷P4799题目描述很简单：给定n场比赛的门票价格和总预算m，求所有花费不超过m的观赛组合数。当n=40时，直观的暴力枚举法需要检查2^40种可能性——这个数字大约是1万亿，即使现代计算机每秒处理1亿次运算，也需要近3小时才能完成。

# 暴力枚举伪代码（实际不可行） def brute_force(prices, budget): n = len(prices) count = 0 for mask in range(1 << n): # 遍历所有子集 total = 0 for i in range(n): if mask & (1 << i): total += prices[i] if total <= budget: count += 1 return count

暴力解法的瓶颈在于：

• 指数级增长：每增加一场比赛，可能性就翻倍
• 重复计算：没有利用子问题之间的相似性
• 单线程处理：没有发挥现代CPU的多核优势

2. 折半搜索的核心思想

折半搜索的精髓在于分而治之，它将原问题拆分为两个规模减半的子问题：

1. 将n场比赛平分为两组（各约n/2场）
2. 分别枚举两组的所有可能组合及花费
3. 合并两组结果，统计满足总预算的组合数

这种策略将复杂度从O(2^n)降为O(n*2^(n/2))。对于n=40的情况，2^20≈100万，使得计算变得可行。

2.1 算法步骤详解

步骤一：问题分割

// 将40场比赛分为前20场和后20场 const int half = n / 2; // 20

步骤二：前半部分枚举

vector<long long> left_sums; for (int mask = 0; mask < (1 << half); ++mask) { long long sum = 0; for (int i = 0; i < half; ++i) { if (mask & (1 << i)) sum += prices[i]; } left_sums.push_back(sum); } sort(left_sums.begin(), left_sums.end()); // 关键排序

步骤三：后半部分处理与合并

long long answer = 0; int right_half = n - half; for (int mask = 0; mask < (1 << right_half); ++mask) { long long sum = 0; for (int i = 0; i < right_half; ++i) { if (mask & (1 << i)) sum += prices[half + i]; } // 在左半部分查找<= (m - sum)的数量 auto it = upper_bound(left_sums.begin(), left_sums.end(), m - sum); answer += (it - left_sums.begin()); }

3. 关键优化技术解析

3.1 排序与二分查找的协同

算法效率提升的关键在于：

1. 对前半部分的结果排序（O(2^(n/2) log(2^(n/2)))）
2. 对每个后半部分的组合，用二分查找快速统计有效配对（O(log(2^(n/2)))）

// upper_bound返回第一个大于m-sum的元素迭代器 // 因此(it - begin)就是<=m-sum的元素数量 auto it = upper_bound(left_sums.begin(), left_sums.end(), m - sum); answer += (it - left_sums.begin());

3.2 边界情况处理

实际编码时需注意：

• 奇偶分组处理（n为奇数时）
• 整数溢出问题（使用long long）
• 空集情况（预算为0或最小票价>m）

// 处理n为奇数的情况 int half = n / 2; // 自动向下取整 int right_half = n - half; // 可能比half大1

4. 完整C++实现与性能分析

以下是经过优化的完整实现：

#include <bits/stdc++.h> using namespace std; int main() { int n; long long m; cin >> n >> m; vector<long long> prices(n); for (auto &x : prices) cin >> x; // 前半部分处理 int half = n / 2; vector<long long> left; for (int mask = 0; mask < (1 << half); ++mask) { long long sum = 0; for (int i = 0; i < half; ++i) { if (mask & (1 << i)) sum += prices[i]; } if (sum <= m) left.push_back(sum); } sort(left.begin(), left.end()); // 后半部分处理 long long ans = 0; int right_half = n - half; for (int mask = 0; mask < (1 << right_half); ++mask) { long long sum = 0; for (int i = 0; i < right_half; ++i) { if (mask & (1 << i)) sum += prices[half + i]; } if (sum > m) continue; ans += upper_bound(left.begin(), left.end(), m - sum) - left.begin(); } cout << ans << endl; return 0; }

性能对比表：

5. 应用场景扩展与思维训练

折半搜索不仅适用于购票问题，还能解决许多"超大搜索空间"问题：

1. 子集和问题：找出数组中满足特定和的所有子集
2. 背包问题变种：当物品数量较多但可分割时
3. 密码破解：减少暴力破解的尝试次数
4. 游戏树搜索：如国际象棋的中局计算

举一反三练习：

• 如果要求输出具体方案而不仅是计数，如何修改算法？
• 当每场比赛有不同权重（如观赏价值）时，如何找到最优组合？
• 如果比赛场次增加到50，算法需要如何调整？

// 输出具体方案的扩展实现思路 void print_combinations(const vector<long long>& left, const vector<int>& left_masks, const vector<long long>& right, const vector<int>& right_masks, long long m) { for (int i = 0; i < right.size(); ++i) { auto it = upper_bound(left.begin(), left.end(), m - right[i]); int count = it - left.begin(); for (int j = 0; j < count; ++j) { print_mask(left_masks[j], right_masks[i]); } } }

在实际项目中使用这类算法时，记得考虑以下几点：

• 内存消耗（存储部分结果可能需要大量空间）
• 并行化可能（两部分枚举可以多线程处理）
• 近似解法（当精确解不必要时的更优方案）

折半搜索展现了算法设计中化整为零的智慧，它将看似不可解的问题转化为可管理的子问题。掌握这种思维，你就能在竞赛和实际工程中应对更多复杂挑战。