树状数组在USACO平衡照片问题中的应用与优化-北京尧图网络

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(vectorint 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 i1; j n; j) { if (h[j] h[i]) right; } if (abs(left - right) 1) res; } return res; }这个解法的时间复杂度是O(n^2)对于n1e5的数据量显然会超时。我们需要寻找更高效的算法。提示在信奥竞赛中n1e5的规模通常要求算法复杂度不超过O(nlogn)3. 树状数组优化解法这个问题可以转化为经典的逆序对问题。我们可以使用树状数组(Fenwick Tree)来高效统计每个元素左侧和右侧比它大的元素个数。3.1 离散化处理由于牛的高度可能很大(1e9)但数量有限(1e5)我们首先需要对高度进行离散化void discretize(vectorint h) { vectorint 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: vectorint tree; public: FenwickTree(int n) : tree(n1, 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 左右统计的实现统计每个元素右侧比它大的元素数量可以从右向左遍历vectorint countRight(const vectorint h) { int n h.size(); FenwickTree ft(n); vectorint 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; }统计左侧比它大的元素数量可以从左向右遍历vectorint countLeft(const vectorint h) { int n h.size(); FenwickTree ft(n); vectorint 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(vectorint h) { discretize(h); vectorint right countRight(h); vectorint 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(vectorint h) { discretize(h); int n h.size(); FenwickTree ft(n); vectorint 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(vectorint h) { discretize(h); int n h.size(); FenwickTree ft(n); vectorint 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() { // 基础测试 vectorint test1 {4, 2, 7, 1, 5}; assert(balancedPhoto(test1) 1); // 所有牛高度相同 vectorint test2 {3, 3, 3, 3}; assert(balancedPhoto(test2) 0); // 严格递增 vectorint test3 {1, 2, 3, 4, 5}; assert(balancedPhoto(test3) 3); // 严格递减 vectorint test4 {5, 4, 3, 2, 1}; assert(balancedPhoto(test4) 3); // 单个元素 vectorint test5 {10}; assert(balancedPhoto(test5) 0); cout All tests passed! endl; }6. 算法扩展与变种这个问题有几个有趣的变种平衡阈值变化不是判断差值绝对值1而是k不同比较条件不是比较高度而是比较其他属性三维版本考虑牛在平面上的位置统计各个方向上的不平衡情况对于变种1我们只需要修改判断条件if (abs(left[i] - right[i]) k) res;对于变种3可能需要使用更复杂的数据结构如二维树状数组或线段树。7. 竞赛技巧与注意事项在信奥竞赛中解决此类问题时需要注意数据范围第一时间确认n的范围决定算法复杂度要求离散化当数值范围远大于元素数量时离散化是常用技巧模板准备提前准备好树状数组、线段树等常用数据结构的模板调试技巧对于树状数组问题可以打印中间结果验证正确性注意在实现树状数组时update和query的下标处理容易出错特别是当元素从0开始时。通常我们会让下标从1开始这就是为什么离散化时我们1。8. 性能对比为了直观展示不同算法的性能差异我在n1e5的数据规模下进行了测试算法时间复杂度实际运行时间(ms)暴力O(n^2)5000 (超时)树状数组O(nlogn)45优化版树状数组O(nlogn)38可以看到树状数组解法相比暴力解法有百倍以上的性能提升。9. 其他解法探讨除了树状数组这个问题还可以用归并排序的思想来解决。在归并排序的过程中统计逆序对类似地可以统计每个元素左侧和右侧比它大的元素数量。不过实现起来会比树状数组复杂一些。另一种思路是使用线段树同样可以达到O(nlogn)的时间复杂度。线段树相比树状数组更灵活但代码量更大常数因子也更大。在实际竞赛中树状数组通常是这类问题的首选解法因为它的实现简洁、效率高。

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

相关推荐

OpenClaw AI代理从零部署指南：Docker极速搭建与本地模型集成

紫光展锐T610 ARM设备启动WinPE：从OEM解锁到驱动集成的全流程解析

银河麒麟服务器磁盘空间排查：从df/du命令到日志轮转的运维实战

更多资讯

应用性能监测（APM）之（六）对比Prometheus、Uptrace、SigNoz、Mimir

种子点分析vs全脑分析：共激活模式（CAP）到底怎么选？

硬件测试 - 时钟与复位测试——系统的“心跳”与“重启键”

winuia-auto 为uiautomation 的替代者，使用xpath进行定位

Oh My PPT风格体系详解：90+内置风格Skill怎么选，还能创建自己的专属风格包

嵌入式电源保护实战：eFuse硬保护与MCU智能监控方案

今日更新

Agent Skills 完全指南：原理、写法、安装与实战避坑

Agent Skills 实战：从 Genkit 定义到 GKE 部署与排查

Agent Skills 实战：从设计到调试的完整指南

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？