![题解：洛谷 P2909 [USACO08OPEN] Cow Cars S](http://pic.xiahunao.cn/yaotu/题解：洛谷 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_iSi1 ≤ S i ≤ 1 , 000 , 000 1 \leq S_i \leq 1,000,0001≤Si≤1,000,000公里/小时行驶。在经历了其他糟糕的驾驶体验后奶牛们讨厌碰撞并采取了极端措施来避免它们。在这条高速公路上奶牛i ii会因为在它前面的每一头奶牛而将速度减少D DD0 ≤ 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 LL1 ≤ L ≤ 1 , 000 , 000 1 \leq L \leq 1,000,0001≤L≤1,000,000公里/小时行驶因此有时一些奶牛在遵循上述规则时将无法上高速公路。编写一个程序找出在遵守最低速度限制法的情况下能够在高速公路上行驶的最大奶牛数量。【输入】* 第 1 行四个以空格分隔的整数N NNM MMD DD和L LL* 第 2 行到第N 1 N1N1行第i 1 i1i1行用一个整数描述奶牛i ii的初始速度S i S_iSi【输出】* 第 1 行一个整数表示可以使用高速公路的最大奶牛数量【输入样例】3 1 1 5 5 7 5【输出样例】2【核心思想】问题分析给定N NN头奶牛的初始速度S i S_iSiM 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⌋计算当前牛前面的牛数量。算法选择贪心排序按速度从小到大排序优先安排速度慢的奶牛。因为速度慢的奶牛对减速更敏感先安排可确保它们在K KK较小时就满足条件车道轮询模拟K a n s / M K ans / MKans/M表示当前要安排的牛前面已有的牛数已安排的a n s ansans头牛平均分配到M MM条车道每条车道有K KK或K 1 K1K1头关键步骤读取输入N , M , D , L N, M, D, LN,M,D,L和N NN个速度S i S_iSi排序sort(a1, aN1)速度升序贪心安排i ii从1 11到N NNK a n s / M K ans / MKans/M当前牛若加入前面平均有K KK头牛若S i − K × D ≥ L S_i - K \times D \ge LSi−K×D≥L满足限速a n s 1 ans \mathrel{} 1ans1输出a n s ansans时间/空间复杂度时间复杂度O ( N log N ) O(N \log N)O(NlogN)排序主导空间复杂度O ( N ) O(N)O(N)存储速度数组贪心排序的核心思想慢牛优先速度慢的奶牛对减速更敏感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的计算方式和排序策略【解题思路】【算法标签】#普及- #贪心【代码详解】#includebits/stdc.husingnamespacestd;intn,m,d,l,a[50005],ans0;intmain(){cinnmdl;// 输入n、m、d和lfor(inti1;in;i){// 输入n个奶牛的速度cina[i];}sort(a1,an1);// 按照从小到大排序不能将小的放后面因为s-k*d后越来越小for(inti1;in;i){// 遍历n头奶牛intkans/m;// 计算k值将多个ans放到不同m中如ans 1和2对应k 1ans 3和4对应k 2if(a[i]-k*dl)ans;// 按照题意车速不能低于l}coutansendl;// 输出结果return0;}【运行结果】3 1 1 5 5 7 5 2
本文分享的必刷题目是从蓝桥云课、洛谷、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_iSi1 ≤ S i ≤ 1 , 000 , 000 1 \leq S_i \leq 1,000,0001≤Si≤1,000,000公里/小时行驶。在经历了其他糟糕的驾驶体验后奶牛们讨厌碰撞并采取了极端措施来避免它们。在这条高速公路上奶牛i ii会因为在它前面的每一头奶牛而将速度减少D DD0 ≤ 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 LL1 ≤ L ≤ 1 , 000 , 000 1 \leq L \leq 1,000,0001≤L≤1,000,000公里/小时行驶因此有时一些奶牛在遵循上述规则时将无法上高速公路。编写一个程序找出在遵守最低速度限制法的情况下能够在高速公路上行驶的最大奶牛数量。【输入】* 第 1 行四个以空格分隔的整数N NNM MMD DD和L LL* 第 2 行到第N 1 N1N1行第i 1 i1i1行用一个整数描述奶牛i ii的初始速度S i S_iSi【输出】* 第 1 行一个整数表示可以使用高速公路的最大奶牛数量【输入样例】3 1 1 5 5 7 5【输出样例】2【核心思想】问题分析给定N NN头奶牛的初始速度S i S_iSiM 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⌋计算当前牛前面的牛数量。算法选择贪心排序按速度从小到大排序优先安排速度慢的奶牛。因为速度慢的奶牛对减速更敏感先安排可确保它们在K KK较小时就满足条件车道轮询模拟K a n s / M K ans / MKans/M表示当前要安排的牛前面已有的牛数已安排的a n s ansans头牛平均分配到M MM条车道每条车道有K KK或K 1 K1K1头关键步骤读取输入N , M , D , L N, M, D, LN,M,D,L和N NN个速度S i S_iSi排序sort(a1, aN1)速度升序贪心安排i ii从1 11到N NNK a n s / M K ans / MKans/M当前牛若加入前面平均有K KK头牛若S i − K × D ≥ L S_i - K \times D \ge LSi−K×D≥L满足限速a n s 1 ans \mathrel{} 1ans1输出a n s ansans时间/空间复杂度时间复杂度O ( N log N ) O(N \log N)O(NlogN)排序主导空间复杂度O ( N ) O(N)O(N)存储速度数组贪心排序的核心思想慢牛优先速度慢的奶牛对减速更敏感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的计算方式和排序策略【解题思路】【算法标签】#普及- #贪心【代码详解】#includebits/stdc.husingnamespacestd;intn,m,d,l,a[50005],ans0;intmain(){cinnmdl;// 输入n、m、d和lfor(inti1;in;i){// 输入n个奶牛的速度cina[i];}sort(a1,an1);// 按照从小到大排序不能将小的放后面因为s-k*d后越来越小for(inti1;in;i){// 遍历n头奶牛intkans/m;// 计算k值将多个ans放到不同m中如ans 1和2对应k 1ans 3和4对应k 2if(a[i]-k*dl)ans;// 按照题意车速不能低于l}coutansendl;// 输出结果return0;}【运行结果】3 1 1 5 5 7 5 2
