2020-07-07 个人赛2 D:Race
比赛的时候，自己没有思考的很清楚，用了一种贪心策略a了，但是赛后无法证明是对的（数据水），所以用正常的思路再次ac掉本题。
题面：
题意：B在进行K米跑步比赛，B起始速度为0。在每一秒首，B可以选择速度+1，不变或者-1（不能小于等于0，且速度姑且认为是突变的），且在冲线时速度必须小于等于X。N次询问，问每次跑步的最短时间。（输出整秒）
题解：简单分类+二分答案
情况①：如果一直加速直到x，行驶的路程大于等于K，这意味着最短时间就是一直加速的情况，所以直接通过x * (x + 1) / 2 >= k，解出x取上整。
情况②：在不满足情况①的时候，可以将整个比赛行程分成加速，匀速（大不了认为匀速时间为0嘛），减速，这三个阶段。
我们可以二分加速的时间为mid（因为加速的时间越长，可以认为答案越符合题意，越优）
加速时间为：mid 加速路程为：(1+mid)*mid/2
减速时间为：mid-x 减速路程为：(mid-1+x)*(mid-x)/2
如果 加速路程+减速路程>K，二分的答案太大，缩小右边界
否则 存在匀速部分，匀速路程为：K-(加速路程+减速路程)，匀速时间为：(匀速路程/mid)取上整。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll k, n, x;///k:长度 x终点速度 cin >> k >> n; while (n--) { cin >> x; ll ans = 1e9 + 7; ///x秒加速的距离超过k 说明可以不断加速 if (x * (x + 1) / 2 >= k) ans = ceil(sqrt(2 * k + 0.25) - 0.5); else { ll l = x, r = 100000; while (l <= r)//[1, mid]加速 [mid, mid + mid - x]减速 { ll mid = (l + r) / 2; ll add_time = mid; ll add = (1 + mid) * mid / 2; ll sub_time = mid - x; ll sub = (mid + x - 1) * (mid - x) / 2; if (add + sub > k) { r = mid - 1; } else { l = mid + 1; ll avg = k - add - sub; ll avg_time = (avg + mid - 1) / mid;//取上整 ans = min(ans, add_time + sub_time + avg_time); } } } cout << ans << endl; } return 0; }
原文：https://www.cnblogs.com/ZJNU-huyh/p/13325157.html