自动搬运

查看原文

来自洛谷，原作者为

	Sunset_afterglow Wir werden den Zweiten Weltkrieg gewinnen || 我是羊我要开始说谎了 || 壶关条件：蓝题 50+ & 橙名及以上 & 除CTJ的人 || 人会背叛但OI不会，不会就是不会，怎么学都不会--Empty_Dream

搬运于2025-08-24 23:04:27，当前版本为作者最后更新于2024-10-23 21:00:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

题目要你求出在什么时间，细菌的数量刚好等于 $m$，细菌 $i$ 在第 $T$ 秒时将分裂出
$ f(T , i) = \begin{cases} 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记录