题解：洛谷 P1842 [USACO05NOV] 奶牛玩杂技-北京尧图网络

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1842 [USACO05NOV] 奶牛玩杂技 - 洛谷【题目描述】Farmer John 养了N NN头牛她们已经按1 ∼ N 1\sim N1∼N依次编上了号。FJ 所不知道的是他的所有牛都梦想着从农场逃走去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳她们还尝试过把自己装在大炮里发射出去但可想而知结果是悲惨的。最终她们决定练习一种最简单的杂技把所有牛都摞在一起比如说第一头牛站在第二头的身上同时第二头牛又站在第三头牛的身上…最底下的是第N NN头牛。每头牛都有自己的体重以及力量编号为i ii的奶牛的体重为W i W_iWi力量为S i S_iSi。当某头牛身上站着另一些牛时它就会在一定程度上被压扁我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛她的压扁指数等于摞在她上面的所有奶牛的总重当然不包括她自己减去它的力量。奶牛们按照一定的顺序摞在一起后她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。你的任务就是帮助奶牛们找出一个摞在一起的顺序使得总压扁指数最小。【输入】第一行一个整数N NN。接下来N NN行每行两个整数W i W_iWi和S i S_iSi。【输出】一行一个整数表示最小总压扁指数。【输入样例】3 10 3 2 5 3 3【输出样例】2【核心思想】问题分析给定N NN头牛每头牛有体重W i W_iWi和力量S i S_iSi。将它们按某种顺序从下到上叠放每头牛的压扁指数上方所有牛的总重− -−该牛的力量。求所有叠放顺序中最大压扁指数的最小值。这是一个贪心排序问题关键在于发现按W i S i W_i S_iWiSi升序排列可使最大压扁指数最小。算法选择贪心策略按W i S i W_i S_iWiSi体重与力量之和从小到大排序该顺序即为最优叠放顺序风险值计算排序后从下往上叠放维护上方累积重量t tt每头牛的压扁指数为t − S i t - S_it−Si取全局最大值关键步骤读取输入N NN和每头牛的( W i , S i ) (W_i, S_i)(Wi,Si)贪心排序按W i S i W_i S_iWiSi升序排列计算最大压扁指数初始化t 0 t 0t0上方累积重量r e s − ∞ res -\inftyres−∞遍历排序后的牛从下到上r e s max ⁡ ( r e s , t − S i ) res \max(res,\ t - S_i)resmax(res,t−Si)当前牛的压扁指数t W i t \mathrel{} W_itWi将该牛重量加入上方累积重量输出r e s resres时间/空间复杂度时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)排序主导空间复杂度O ( N ) O(N)O(N)存储牛的信息贪心排序的核心思想交换论证考虑相邻两头牛i ii和j jji ii在下j jj在上交换它们不影响其他牛的压扁指数。通过比较交换前后的最大压扁指数可证明当W i S i ≤ W j S j W_i S_i \le W_j S_jWiSi≤WjSj时原顺序不劣于交换后的顺序局部最优推全局最优相邻交换的贪心选择性质保证了按W S W SWS排序的全局最优性风险累积t tt单调递增力量S i S_iSi较大的牛应放在下方此时t tt较小以减小t − S i t - S_it−Si适用于排序后单调累积求最值类问题核心是通过交换论证发现正确的排序关键字【算法标签】#普及 #贪心【代码详解】#includebits/stdc.husingnamespacestd;constintMAX_N50004;// 定义最大牛的数量intn;// 牛的数量intres-1e9;// 存储最终结果最大风险值intt;// 当前累积的重量// 定义牛的结构体包含重量和力量structNode{intw;// 牛的重量ints;// 牛的力量// 重载小于运算符用于排序booloperator(Nodet){returnwst.wt.s;}}a[MAX_N];// 存储所有牛的信息intmain(){// 输入牛的数量cinn;// 输入每头牛的重量和力量for(inti1;in;i)cina[i].wa[i].s;// 按照ws升序排序sort(a1,an1);// 计算最大风险值for(inti1;in;i){// 当前牛的风险值上方所有牛的重量 - 当前牛的力量resmax(res,t-a[i].s);// 累加当前牛的重量ta[i].w;}// 输出结果coutresendl;return0;}【运行结果】3 10 3 2 5 3 3 2

题解：洛谷 P1842 [USACO05NOV] 奶牛玩杂技

相关推荐

阿里云企业网络 + ECS部署---实战

Textual InlineStyle深度解析：代码、强调、链接等行内元素样式定制全攻略

BP神经网络房价预测：从特征工程到误差评估的完整回归基线

更多资讯

快降重理工科降AI技术：实证数据与推导逻辑的保护机制详解

YimMenu：GTA V 防崩溃菜单，怎么编译注入、哪些功能敢开

Visual Studio 添加万能头文件 bits/stdc++.h：从原理到配置全程指南

Windows平台frpc客户端架构选择与性能优化指南

PaddleHelix 分子模型上手指南：GeoGNN 与 SD VAE 两个核心组件从原理到跑通

企业级数据可视化BI 仪表板数据中台监控平台的选择分析

今日更新

MATLAB缩进快捷键与批量格式化实战指南

用Poco实现Qt风格信号与槽的跨平台C++方案

ESXi裸机虚拟化安装指南：从硬件兼容到虚拟机部署

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

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

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

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

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