题解：P11125 [ROIR 2024 Day 2] 细菌

· · 题解

题意

题目要你求出在什么时间，细菌的数量刚好等于 m，细菌 i 在第 T 秒时将分裂出

2^{T - a_i - t_i + 1} & T - a_i - t_i + 1 > 0 & a_i \le k \\ 1 & a_i \le k \\ 0 & a_i > k \\ \end{cases}

思路

因为我们发现这道题目的答案具有单调性，所以我们可以使用二分答案来求出在第一次细菌数量刚好等于 m 的时间。

解法

这道题目的关键在于二分答案的 check 函数如何写，其实很简单，我们直接按照上面的公式把 T 带入就可以得出在第 T 秒时将分裂出 \sum_{i = 1}^{n} f(T , i) 个细菌。

最后的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int N = 2e5 + 10;
int n,m,a[N],t[N];
int power(int b) {
    int ans=1,t=2;
    bool flag=0;
    while(b){
        if(b&1){
            if(flag) return -1;
            ans*=t;
            if(ans>m) return -1;
        }
        t=t*t;
        if(t>m) flag=1;
        b>>=1;
    }
    return ans;
}
int check(int k){
    int ans=0;
    for(int i=1;i<=n;++i){
        if(a[i]<=k&&a[i]+t[i]-1>=k)++ans; 
        else if(a[i]<=k){
            int tmp=power(k-t[i]-a[i]+1);
            if(tmp==-1)return m+1;
            ans+=tmp;
            if(ans>m)return LLONG_MAX;
        }
    }
    return ans;
}
signed main(){
    n = read(); m = read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)t[i]=read();
    int l=1,r=6e9,ans=-1;
    while(l<=r){
        int mid=l+r>>1,t=check(mid);
//      cout<<l<<' '<<r<<' '<<mid<<' '<<t<<'\n';
        if(t<m) l=mid+1;
        else {
            if(t==m){
                ans=mid;
            }
            r=mid-1;
        }
    }
    if(ans!=-1&&check(ans))cout<<ans;
    else cout<<-1;
    return 0;
}

AC记录