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 合并左右统计

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

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

这样可以减少代码量：

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 边界条件处理

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

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

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

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; }

6. 算法扩展与变种

这个问题有几个有趣的变种：

1. 平衡阈值变化：不是判断差值绝对值>1，而是>k
2. 不同比较条件：不是比较高度，而是比较其他属性
3. 三维版本：考虑牛在平面上的位置，统计各个方向上的不平衡情况

对于变种1，我们只需要修改判断条件：

if (abs(left[i] - right[i]) > k) res++;

对于变种3，可能需要使用更复杂的数据结构，如二维树状数组或线段树。

7. 竞赛技巧与注意事项

在信奥竞赛中解决此类问题时，需要注意：

1. 数据范围：第一时间确认n的范围，决定算法复杂度要求
2. 离散化：当数值范围远大于元素数量时，离散化是常用技巧
3. 模板准备：提前准备好树状数组、线段树等常用数据结构的模板
4. 调试技巧：对于树状数组问题，可以打印中间结果验证正确性

注意：在实现树状数组时，update和query的下标处理容易出错，特别是当元素从0开始时。通常我们会让下标从1开始，这就是为什么离散化时我们"+1"。

8. 性能对比

为了直观展示不同算法的性能差异，我在n=1e5的数据规模下进行了测试：

可以看到，树状数组解法相比暴力解法有百倍以上的性能提升。

9. 其他解法探讨

除了树状数组，这个问题还可以用归并排序的思想来解决。在归并排序的过程中统计逆序对，类似地可以统计每个元素左侧和右侧比它大的元素数量。不过实现起来会比树状数组复杂一些。

另一种思路是使用线段树，同样可以达到O(nlogn)的时间复杂度。线段树相比树状数组更灵活，但代码量更大，常数因子也更大。

在实际竞赛中，树状数组通常是这类问题的首选解法，因为它的实现简洁、效率高。