题解：洛谷 P2909 [USACO08OPEN] Cow Cars S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

---

【题目来源】

洛谷：P2909 [USACO08OPEN] Cow Cars S - 洛谷

【题目描述】

在 Cowtopia 的高速公路上，有N NN头奶牛（1 ≤ N ≤ 50 , 000 1 \leq N \leq 50,0001≤N≤50,000），它们被方便地编号为1.. N 1..N1..N，分别驾驶着不同的汽车。奶牛i ii可以在M MM条不同的高速车道上行驶（1 ≤ M ≤ N 1 \leq M \leq N1≤M≤N），并且可以以最大速度S i S_iSi​（1 ≤ S i ≤ 1 , 000 , 000 1 \leq S_i \leq 1,000,0001≤Si​≤1,000,000）公里/小时行驶。

在经历了其他糟糕的驾驶体验后，奶牛们讨厌碰撞，并采取了极端措施来避免它们。在这条高速公路上，奶牛i ii会因为在它前面的每一头奶牛而将速度减少D DD（0 ≤ D ≤ 5 , 000 0 \leq D \leq 5,0000≤D≤5,000）公里/小时（但速度不会低于 0 公里/小时）。因此，如果在奶牛i ii前面有K KK头奶牛，那么它将以max ⁡ [ S i − D × K , 0 ] \max[S_i - D \times K, 0]max[Si​−D×K,0]的速度行驶。虽然奶牛实际上可能比直接在它前面的奶牛行驶得更快，但奶牛之间的间距足够大，因此一旦奶牛减速，就不会发生碰撞。

Cowtopia 有一条最低速度法则，要求高速公路上的所有车辆都必须以最低速度L LL（1 ≤ L ≤ 1 , 000 , 000 1 \leq L \leq 1,000,0001≤L≤1,000,000）公里/小时行驶，因此有时一些奶牛在遵循上述规则时将无法上高速公路。编写一个程序，找出在遵守最低速度限制法的情况下，能够在高速公路上行驶的最大奶牛数量。

【输入】

* 第 1 行：四个以空格分隔的整数：N NN，M MM，D DD和L LL

* 第 2 行到第N + 1 N+1N+1行：第i + 1 i+1i+1行用一个整数描述奶牛i ii的初始速度：S i S_iSi​

【输出】

* 第 1 行：一个整数，表示可以使用高速公路的最大奶牛数量

【输入样例】

3 1 1 5 5 7 5

【输出样例】

2

【核心思想】

1. 问题分析：给定N NN头奶牛的初始速度S i S_iSi​，M MM条车道，减速规则为前面有K KK头牛时速度变为max ⁡ ( S i − D × K , 0 ) \max(S_i - D \times K, 0)max(Si​−D×K,0)，最低限速为L LL。求能上高速的最大奶牛数量。这是一个贪心排序 + 模拟分配问题，关键在于将速度慢的奶牛优先安排（减少后续减速影响），并用K = ⌊ 已安排数 / M ⌋ K = \lfloor \text{已安排数} / M \rfloorK=⌊已安排数/M⌋计算当前牛前面的牛数量。

2. 算法选择：

   • 贪心排序：按速度从小到大排序，优先安排速度慢的奶牛。因为速度慢的奶牛对减速更敏感，先安排可确保它们在K KK较小时就满足条件
   • 车道轮询模拟：K = a n s / M K = ans / MK=ans/M表示当前要安排的牛前面已有的牛数（已安排的a n s ansans头牛平均分配到M MM条车道，每条车道有K KK或K + 1 K+1K+1头）

3. 关键步骤：

   • 读取输入：N , M , D , L N, M, D, LN,M,D,L和N NN个速度S i S_iSi​
   • 排序：sort(a+1, a+N+1)，速度升序
   • 贪心安排（i ii从1 11到N NN）：
     • K = a n s / M K = ans / MK=ans/M：当前牛若加入，前面平均有K KK头牛
     • 若S i − K × D ≥ L S_i - K \times D \ge LSi​−K×D≥L：满足限速，a n s + = 1 ans \mathrel{+}= 1ans+=1
   • 输出a n s ansans

4. 时间/空间复杂度：

   • 时间复杂度：O ( N log ⁡ N ) O(N \log N)O(NlogN)，排序主导
   • 空间复杂度：O ( N ) O(N)O(N)，存储速度数组

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

   • 慢牛优先：速度慢的奶牛对减速更敏感（S i − K × D S_i - K \times DSi​−K×D更容易低于L LL），优先安排可确保它们在K KK较小时就被选中
   • 车道均衡：a n s / M ans / Mans/M假设牛被均衡分配到M MM条车道，当前新牛加入任一车道的最坏情况就是前面有⌈ a n s / M ⌉ \lceil ans / M \rceil⌈ans/M⌉头牛。由于我们按最坏情况估计（K = ⌊ a n s / M ⌋ K = \lfloor ans / M \rfloorK=⌊ans/M⌋），若此时满足条件则实际安排一定可行
   • 最优性保证：将速度慢的牛放在前面，快的牛放在后面承受更多减速但仍可能满足条件，这是最大化数量的最优策略
   • 适用于"排序后贪心验证 + 资源均衡分配"类问题，核心是理解K KK的计算方式和排序策略

【解题思路】

【算法标签】

#普及- #贪心

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,m,d,l,a[50005],ans=0;intmain(){cin>>n>>m>>d>>l;// 输入n、m、d和lfor(inti=1;i<=n;i++){// 输入n个奶牛的速度cin>>a[i];}sort(a+1,a+n+1);// 按照从小到大排序（不能将小的放后面，因为s-k*d后越来越小）for(inti=1;i<=n;i++){// 遍历n头奶牛intk=ans/m;// 计算k值，将多个ans放到不同m中，如ans 1和2对应k 1，ans 3和4对应k 2if(a[i]-k*d>=l)ans++;// 按照题意，车速不能低于l}cout<<ans<<endl;// 输出结果return0;}

【运行结果】

3 1 1 5 5 7 5 2