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

树状数组在USACO平衡照片问题中的应用与优化

news 2026/8/7 4:02:43

1. 题目背景与需求分析

这道题目来自USACO 2017年1月银组竞赛，编号P3608。题目名为"Balanced Photo G"，属于典型的数组处理类问题。题目大意是：给定N头牛排成一列，每头牛有一个高度h_i。我们需要统计有多少头牛满足"不平衡"的条件——即在这头牛的左侧，比它高的牛的数量与右侧比它高的牛的数量之差绝对值大于1。

举个例子，假设有5头牛，高度分别为[4, 2, 7, 1, 5]。对于第3头牛(高度7)来说：

左侧比它高的牛数量：0
右侧比它高的牛数量：0
差值绝对值为0，所以这头牛是"平衡"的

而第1头牛(高度4)：

左侧比它高的牛数量：0
右侧比它高的牛数量：1（高度7）
差值绝对值为1，所以也是"平衡"的

只有当这个差值绝对值>1时，我们才认为这头牛处于"不平衡"状态。

2. 暴力解法与复杂度分析

最直观的解法是对于每头牛，分别向左和向右扫描统计比它高的牛的数量：

int countUnbalanced(vector<int>& h) { int n = h.size(); int res = 0; for (int i = 0; i < n; ++i) { int left = 0, right = 0; // 向左统计 for (int j = 0; j < i; ++j) { if (h[j] > h[i]) left++; } // 向右统计 for (int j = i+1; j < n; ++j) { if (h[j] > h[i]) right++; } if (abs(left - right) > 1) res++; } return res; }

这个解法的时间复杂度是O(n^2)，对于n=1e5的数据量显然会超时。我们需要寻找更高效的算法。

提示：在信奥竞赛中，n=1e5的规模通常要求算法复杂度不超过O(nlogn)

3. 树状数组优化解法

这个问题可以转化为经典的逆序对问题。我们可以使用树状数组(Fenwick Tree)来高效统计每个元素左侧和右侧比它大的元素个数。

3.1 离散化处理

由于牛的高度可能很大(1e9)，但数量有限(1e5)，我们首先需要对高度进行离散化：

void discretize(vector<int>& h) { vector<int> tmp = h; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); for (int& num : h) { num = lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() + 1; } }

离散化后，所有高度都被映射到1-n的范围内，便于树状数组处理。

3.2 树状数组实现

树状数组的核心操作包括点更新和前缀查询：

class FenwickTree { private: vector<int> tree; public: FenwickTree(int n) : tree(n+1, 0) {} void update(int idx, int delta) { while (idx < tree.size()) { tree[idx] += delta; idx += idx & -idx; } } int query(int idx) { int res = 0; while (idx > 0) { res += tree[idx]; idx -= idx & -idx; } return res; } };

3.3 左右统计的实现

统计每个元素右侧比它大的元素数量，可以从右向左遍历：

vector<int> countRight(const vector<int>& h) { int n = h.size(); FenwickTree ft(n); vector<int> right(n); for (int i = n-1; i >= 0; --i) { right[i] = ft.query(n) - ft.query(h[i]); ft.update(h[i], 1); } return right; }

统计左侧比它大的元素数量，可以从左向右遍历：

vector<int> countLeft(const vector<int>& h) { int n = h.size(); FenwickTree ft(n); vector<int> left(n); for (int i = 0; i < n; ++i) { left[i] = ft.query(n) - ft.query(h[i]); ft.update(h[i], 1); } return left; }

3.4 完整解法

将上述部分组合起来：

int balancedPhoto(vector<int>& h) { discretize(h); vector<int> right = countRight(h); vector<int> left = countLeft(h); int res = 0; for (int i = 0; i < h.size(); ++i) { if (abs(left[i] - right[i]) > 1) { res++; } } return res; }

这个算法的时间复杂度为O(nlogn)，可以高效处理1e5规模的数据。

4. 算法优化与细节处理

4.1 合并左右统计

实际上，我们可以通过一次遍历就完成左右统计。具体做法是：

先统计右侧比当前元素大的数量（从右向左）
清空树状数组
再统计左侧比当前元素大的数量（从左向右）

这样可以减少代码量：

int balancedPhotoOpt(vector<int>& h) { discretize(h); int n = h.size(); FenwickTree ft(n); vector<int> right(n), left(n); // 统计right for (int i = n-1; i >= 0; --i) { right[i] = ft.query(n) - ft.query(h[i]); ft.update(h[i], 1); } // 清空树状数组 ft = FenwickTree(n); // 统计left for (int i = 0; i < n; ++i) { left[i] = ft.query(n) - ft.query(h[i]); ft.update(h[i], 1); } int res = 0; for (int i = 0; i < n; ++i) { if (abs(left[i] - right[i]) > 1) res++; } return res; }

4.2 边界条件处理

在实际编码中，需要注意以下边界条件：

数组为空的情况
所有牛高度相同的情况
只有一头牛的情况

我们的代码已经天然处理了这些边界情况，但测试时还是应该特别验证。

4.3 空间优化

如果内存紧张，可以复用同一个数组存储left和right的结果：

int balancedPhotoSpaceOpt(vector<int>& h) { discretize(h); int n = h.size(); FenwickTree ft(n); vector<int> diff(n); // 统计right并直接存储差值 for (int i = n-1; i >= 0; --i) { diff[i] = -(ft.query(n) - ft.query(h[i])); ft.update(h[i], 1); } ft = FenwickTree(n); // 统计left并完成差值计算 int res = 0; for (int i = 0; i < n; ++i) { diff[i] += ft.query(n) - ft.query(h[i]); if (abs(diff[i]) > 1) res++; ft.update(h[i], 1); } return res; }

5. 测试与验证

编写测试用例验证我们的解法：

void test() { // 基础测试 vector<int> test1 = {4, 2, 7, 1, 5}; assert(balancedPhoto(test1) == 1); // 所有牛高度相同 vector<int> test2 = {3, 3, 3, 3}; assert(balancedPhoto(test2) == 0); // 严格递增 vector<int> test3 = {1, 2, 3, 4, 5}; assert(balancedPhoto(test3) == 3); // 严格递减 vector<int> test4 = {5, 4, 3, 2, 1}; assert(balancedPhoto(test4) == 3); // 单个元素 vector<int> test5 = {10}; assert(balancedPhoto(test5) == 0); cout << "All tests passed!" << endl; }