思路:
思路很简单,首先获取输入的H(min)和H(max),在这之间二分枚举,每一次判断是否合法,如果合法则r=mid继续枚举
注意:
每一次判断时,可能会出现爆数据的现象,两种方法解决
1取模,这里取模方式很重要,单独取模e%=mod会出错
2判断 if(e>=ma) return true;
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9;
typedef long long LL;
const int mod = 1e9+7;
int a[N];
int n;
int check(LL e,int ma)
{
for(int i=1;i<=n;i++)
{
//e+=(e-b[i]);
//注意这里要去取模,或者按照 if(e>=ma) return true;
e+=((e-a[i])%mod)%mod;
// e%=mod;
if(e<0) return 0;
// if(e>=ma) return true;
}
// cout<<endl;
return 1;
}
int main()
{
cin>>n;
int ma = -1e9,mi = 1e9;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
ma = max(a[i],ma);
mi = min(mi,a[i]);
}
int l = mi,r = ma;
// cout<<l<<" "<<r<<endl;
//check(65324);
while(l<r)
{
LL mid = (l+r)>>1;
if(check(mid,ma)) r = mid;
else l = mid + 1;
}
cout<<l<<endl;
return 0;
}