欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
【题目来源】
洛谷：[P9948 USACO20JAN] Race B - 洛谷
【题目描述】
Bessie 正在参加一场 **K ( 1 ≤ K ≤ 10 9 ) K(1\le K\le 10^9)K(1≤K≤109)**米的跑步比赛。她从0 00米每秒的速度开始比赛。在每一秒中，她可以选择将她的速度增加1 11米每秒，保持速度不变，或者将她的速度减少1 11米每秒。例如，在第一秒中，她可以将她的速度增加到1 11米每秒，跑1 11米，或者保持她的速度0 00米每秒不变，跑0 00米。Bessie 的速度不会降低到小于零。
Bessie 始终朝着终点线的方向跑，她想要花费整数秒的时间完成比赛。此外，她不想在终点时跑得太快：在 Bessie 跑完K KK米的时刻，她希望她的速度不超过 **X ( 1 ≤ X ≤ 10 5 ) X(1\le X\le 10^5)X(1≤X≤105)米每秒。Bessie 想要对于N ( 1 ≤ N ≤ 1000 ) N(1\le N\le 1000)N(1≤N≤1000)**个不同的X XX值知道她多快可以完成比赛。
【输入】
输入的第一行包含两个整数K KK和N NN。
以下N NN行每行包含一个整数X XX。
【输出】
输出N NN行，每行包含一个整数，表示 Bessie 完成比赛时的速度小于或等于X XX的情况下跑完K KK米需要的最小时间。
【输入样例】
10 5 1 2 3 4 5【输出样例】
6 5 5 4 4【算法标签】
《洛谷 P9948 Race》 #USACO# #O2优化# #2020#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intk,n,x;// ifstream filein("race.in");// ofstream fileout("race.out");intmain(){// filein >> k >> n; // 输入k和ncin>>k>>n;// 输入k和nwhile(n--){// 遍历n次询问// filein >> x; // 输入xcin>>x;// 输入xlonglongpresum=(longlong)(x+1)*x/2;// 求出presum（细节处理，需要加上long long）if(presum>=k){// 如果presum已经超过了k// fileout << ceil(sqrt(2*k+0.25)-0.5) << endl; // 反向求cout<<ceil(sqrt(2*k+0.25)-0.5)<<endl;// 反向求continue;}intl=0,r=(k-presum)/x;// 二分左值为0，右值为(k-presum)/xif((k-presum)%x!=0){// 如果r不为整数，自增1（细节处理）r++;}while(l<r-1){// 二分查找intm=(l+r)/2;// 中间点inttot=k-presum-x*m;// tot为增加面积。（tot+presum+m*x）>= klonglongcmax=0;// 定义cmax，后面需要与tot比较intup=m/2;// up取m的一半if(m%2==0){cmax=(longlong)up*up;// 增加的面积}else{cmax=(longlong)(1+up)*up;// 增加的面积（细节处理）}if(cmax>=tot){// 如果cmax大于等于tot，说明m设大了r=m;}else{// 否则说明设小了l=m;}}// fileout << x+r << endl; // x是presum的时间，r为m这段的时间cout<<x+r<<endl;// x是presum的时间，r为m这段的时间}return0;}【运行结果】
10 5 1 6 2 5 3 5 4 4 5 4
