​Problem - 2149F - Codeforces​

Problem - 2149F - Codeforces大致题意 每次可以选择1. 休息 健康值12. 向右移动减少健康值 如果连续移动j次 那么第j次的代价就是j;显然 假设我们一共休息了m次如果想让用的代价最少 我们一定要将这m次平均分配到整个路程中这样使得花费的代价少中间的每一段花费的总代价可以用等差数列求和来实现如果连续移动的t次 那么代价f(t)(t1)*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 cntd/(x1),resd%(x1); return hx-(x1-res)*(cnt*(cnt1)/2)-res*((cnt2)*(cnt1)/2)0; } void solve(){ cinhd; int ans0; if(h1){ h; ans; } int l0,rd1; while(lr){ int mid(lr)1; if(check(mid)){ rmid; }else lmid1; } coutrdans\n; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t1; cint; while(t--)solve(); return 0; }