P4058 [Code+#1]木材题解

· · 题解

我的解法：即不需要对 n=1 进行特判，也不需要设置unsigned long long类型的变量。而是使用数学的技巧规避了会爆long long的问题。

会爆long long的点

当 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; //需要处理，爆LL
        if(cnt>=s) break;
    }
    if(cnt>=s) return true;
    return false;
}

修改思路

可以把不等式 h[i] + d[i] * x >= l 两边同时整除 d[i]，我们可以这样写 h[i] >= l\ ||\ x >= (l - h[i] - 1) / d[i] + 1 减1再加1是为了保证除法的结果上取整，因为本来是这样: x >= (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