企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、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

【核心思想】

1. 问题分析：给定N NN头牛，每头牛有体重W i W_iWi​和力量S i S_iSi​。将它们按某种顺序从下到上叠放，每头牛的压扁指数 = 上方所有牛的总重− -−该牛的力量。求所有叠放顺序中，最大压扁指数的最小值。这是一个贪心排序问题，关键在于发现按W i + S i W_i + S_iWi​+Si​升序排列可使最大压扁指数最小。

2. 算法选择：

   • 贪心策略：按W i + S i W_i + S_iWi​+Si​（体重与力量之和）从小到大排序，该顺序即为最优叠放顺序
   • 风险值计算：排序后从下往上叠放，维护上方累积重量t tt，每头牛的压扁指数为t − S i t - S_it−Si​，取全局最大值

3. 关键步骤：

   • 读取输入：N NN和每头牛的( W i , S i ) (W_i, S_i)(Wi​,Si​)
   • 贪心排序：按W i + S i W_i + S_iWi​+Si​升序排列
   • 计算最大压扁指数：
     • 初始化t = 0 t = 0t=0（上方累积重量），r e s = − ∞ res = -\inftyres=−∞
     • 遍历排序后的牛（从下到上）：
       • r e s = max ⁡ ( r e s , t − S i ) res = \max(res,\ t - S_i)res=max(res,t−Si​)：当前牛的压扁指数
       • t + = W i t \mathrel{+}= W_it+=Wi​：将该牛重量加入上方累积重量
   • 输出r e s resres

4. 时间/空间复杂度：

   • 时间复杂度：O ( N log ⁡ N ) O(N \log N)O(NlogN)，排序主导
   • 空间复杂度：O ( N ) O(N)O(N)，存储牛的信息

5. 贪心排序的核心思想：

   • 交换论证：考虑相邻两头牛i ii和j jj（i ii在下，j jj在上），交换它们不影响其他牛的压扁指数。通过比较交换前后的最大压扁指数，可证明当W i + S i ≤ W j + S j W_i + S_i \le W_j + S_jWi​+Si​≤Wj​+Sj​时，原顺序不劣于交换后的顺序
   • 局部最优推全局最优：相邻交换的贪心选择性质保证了按W + S W + SW+S排序的全局最优性
   • 风险累积：t tt单调递增，力量S i S_iSi​较大的牛应放在下方（此时t tt较小），以减小t − S i t - S_it−Si​
   • 适用于"排序后单调累积求最值"类问题，核心是通过交换论证发现正确的排序关键字

【算法标签】

#普及 #贪心

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintMAX_N=50004;// 定义最大牛的数量intn;// 牛的数量intres=-1e9;// 存储最终结果（最大风险值）intt;// 当前累积的重量// 定义牛的结构体，包含重量和力量structNode{intw;// 牛的重量ints;// 牛的力量// 重载小于运算符，用于排序booloperator<(Node&t){returnw+s<t.w+t.s;}}a[MAX_N];// 存储所有牛的信息intmain(){// 输入牛的数量cin>>n;// 输入每头牛的重量和力量for(inti=1;i<=n;i++)cin>>a[i].w>>a[i].s;// 按照w+s升序排序sort(a+1,a+n+1);// 计算最大风险值for(inti=1;i<=n;i++){// 当前牛的风险值 = 上方所有牛的重量 - 当前牛的力量res=max(res,t-a[i].s);// 累加当前牛的重量t+=a[i].w;}// 输出结果cout<<res<<endl;return0;}

【运行结果】

3 10 3 2 5 3 3 2