​Problem - 2149F - Codeforces​

Problem - 2149F - Codeforces

大致题意： 每次可以选择
1. 休息 健康值+1
2. 向右移动，减少健康值 如果连续移动j次 那么第j次的代价就是j;
显然 假设我们一共休息了m次，如果想让用的代价最少 ，我们一定要将这m次平均分配到整个路程中，这样使得花费的代价少；

中间的每一段花费的总代价可以用等差数列求和来实现：
如果连续移动的t次 那么代价f(t)=(t+1)*t/2;

假设平均分配后 分成了s段 则d/s 为每一段的长度a 但是由于向下取整，d%s个段会加1

我们可以二分枚举休息的次数m 也就是分成了多少段 ，然后查找即可：

代码如下：

#include <bits/stdc++.h> using namespace std; #define int long long int h,d; bool check(int x){ int cnt=d/(x+1),res=d%(x+1); return h+x-(x+1-res)*(cnt*(cnt+1)/2)-res*((cnt+2)*(cnt+1)/2)>0; } void solve(){ cin>>h>>d; int ans=0; if(h==1){ h++; ans++; } int l=0,r=d+1; while(l<r){ int mid=(l+r)>>1; if(check(mid)){ r=mid; }else l=mid+1; } cout<<r+d+ans<<'\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--)solve(); return 0; }