题解：Codeforces CF1613C Poisoned Dagger

• 标签：二分

题意

给定一个长度为 \(n\) 的序列 \(a\)，定义数 \(k\)，对于 \(i>1\)，如果 \(a_i-a_{i-1}<k\)，\(s\) 加上 \(a_i-a_{i-1}\)，否则加上 \(k\)，求满足 \(s\geq h\) 的最小 \(k\)。

思路

手玩样例，\(k\) 越大龙死的越快，所以具有单调性，考虑二分答案。

每次缩小范围时判断是否 \(k\geq a_i-a_{i-1}\)，模拟即可，不要忘记最后一个也要加上。

不难发现数据大，最好全程开 long long，右指针开到 \(10^{18}\)。

代码

#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c) for(i64 i=a;i<=b;i+=c)
#define R(a,b,c) for(int i=a;i>=b;i-=c)

using namespace std;

const int N=1e5+5,M=998244353;

i64 T,n,h,a[105];

void solve();

signed main(){
  ios::sync_with_stdio(0);
  
  solve();
  
  return 0;
}

bool check(i64 s){
  i64 sum=0;
  L(2,n,1){
    if(a[i]-a[i-1]<s) sum+=a[i]-a[i-1];
    else sum+=s;
  }
  sum+=s;
  return sum<h;
}

void solve(){
  cin>>T;
  while(T--){
    cin>>n>>h;
    L(1,n,1) cin>>a[i];
    i64 l=1,r=1e18,m;
    while(l<=r){
      m=(l+r)>>1;
      if(check(m)) l=m+1;
      else r=m-1;
    }
    cout<<r+1<<endl;
  }
}