坑点
当 $H=1,A=1,L=10^{18}$ 时,需要的月份就是 $10^{18}$,而check函数中的乘法运算:$A[i] \cdot x$,最大可以到 $10^9 \cdot 10^{18} = 10^{27}$,这里需要特殊处理check函数,即把乘法变成除法。
本来我是这么写的,没考虑乘法溢出
bool check(LL x){
LL cnt=0;
for(int i=0;i<n;i++){
if(h[i]+d[i]*x>=l) cnt+=h[i]+d[i]*x; //需要处理
if(cnt>=s) break;
}
if(cnt>=s) return true;
return false;
}
修改思路
原来不是 $h[i] + d[i] * x >= l$ 吗,我们可以这样写 $h[i] \ge l\ ||\ x \ge (l - h[i] - 1) / d[i] + 1$ 减1再加1是为了保证除法的结果上取整,因为本来是这样: $x \ge (l-h[i])/d[i]$,如果右边的 $(l-h[i])/d[i]$ 是小数且大于x时,比如 $x=5 右边=5.1$,本来右边是大于x的,但由于c++的整除去掉小数,右边变成5了,这时左右变成相等了,就错了,所以右边对小数部分要上取整,如右边等于 $5.1$ 上取整变为6,才是正解。
bool check(LL x){
LL cnt=0;
for(int i=0;i<n;i++){
if(h[i]>=l || x>=(l-h[i]-1)/d[i]+1){
if(h[i]>=s || x>=(s-h[i]-1)/d[i]+1){
return true;
}
cnt+=h[i]+x*d[i];
}
if(cnt>=s) return true;
}
return false;
}
就是当x很大时,判断一下直接返回真
全部代码
#include <cstdio>
using namespace std;
const int N=2e5+10;
typedef long long LL;
LL s,l;
int n,h[N],d[N];
bool check(LL x){
LL cnt=0;
for(int i=0;i<n;i++){
if(h[i]>=l || x>=(l-h[i]-1)/d[i]+1){
if(h[i]>=s || x>=(s-h[i]-1)/d[i]+1){
return true;
}
cnt+=h[i]+x*d[i];
}
if(cnt>=s) return true;
}
return false;
}
int main(){
scanf("%d%lld%lld",&n,&s,&l);
for(int i=0;i<n;i++) scanf("%d",&h[i]);
for(int i=0;i<n;i++) scanf("%d",&d[i]);
LL l=0,r=1e18;
while(l<r){
LL mid=(l+r)/2;
bool f;
if((f=check(mid))) r=mid;
else l=mid+1;
}
printf("%lld\n",l);
return 0;
}
补充
有人说,这道题特判一下1,就可以过,确实再洛谷AC了,如果你那么搞了,我可以很容易构造出一组数据,让你的代码WA,因为,经过我的计算,当左边界为0,右边界为$10^{18}$时,前20个$d[i]\cdot x$都超过$10^{20}$.
计算代码:
#include <cstdio>
using namespace std;
int main(){
double n=1e18;
for(int i=0;i<20;i++){
n/=2.0;
double ans=n*1e9;
printf("%d :%g,ans=%g\n",i+1,n,ans);
}
return 0;
}
计算结果:
1 :5e+17,ans=5e+26
2 :2.5e+17,ans=2.5e+26
3 :1.25e+17,ans=1.25e+26
4 :6.25e+16,ans=6.25e+25
5 :3.125e+16,ans=3.125e+25
6 :1.5625e+16,ans=1.5625e+25
7 :7.8125e+15,ans=7.8125e+24
8 :3.90625e+15,ans=3.90625e+24
9 :1.95312e+15,ans=1.95313e+24
10 :9.76562e+14,ans=9.76563e+23
11 :4.88281e+14,ans=4.88281e+23
12 :2.44141e+14,ans=2.44141e+23
13 :1.2207e+14,ans=1.2207e+23
14 :6.10352e+13,ans=6.10352e+22
15 :3.05176e+13,ans=3.05176e+22
16 :1.52588e+13,ans=1.52588e+22
17 :7.62939e+12,ans=7.62939e+21
18 :3.8147e+12,ans=3.8147e+21
19 :1.90735e+12,ans=1.90735e+21
20 :9.53674e+11,ans=9.53674e+20