Educational Codeforces Round 61 D 二分 + 线段树

时间:2022-07-29 05:35:35

https://codeforces.com/contest/1132/problem/D

二分 + 线段树(弃用结构体型线段树)

题意

有n台电脑,只有一个充电器,每台电脑一开始有a[i]电量,每秒消耗b[i]电量,充电器每秒可以给一台电脑充x电,假如有一台电脑在某一秒末电量<0,则会关机,问最小的x使得在k秒内没有任何电脑关机

题解

  • 二分答案x,线段树维护区间[1,n]最小天数,枚举k天每天单点修改天数最小的点

代码

#include<bits/stdc++.h>
#define M 200005
#define ll long long
using namespace std;
ll a[M],b[M],mn[M*4],lt[M*4],l,r,mid;
int n,k,i; void build(int o,int l,int r){
if(l==r){
mn[o]=a[l]/b[l];lt[o]=a[l]%b[l];
return;
}
int mid=(l+r)/2;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
mn[o]=min(mn[o<<1],mn[o<<1|1]);
return;
}
void ud(int o,int l,int r,ll x){
if(l==r){
mn[o]+=x/b[l];
lt[o]+=x%b[l];
mn[o]+=lt[o]/b[l];
lt[o]=lt[o]%b[l];
return;
}
int ls=o<<1,rs=o<<1|1,mid=(l+r)/2;
if(mn[ls]<=0&&mn[rs]<=0)return;
if(mn[ls]<mn[rs])ud(ls,l,mid,x);
else ud(rs,mid+1,r,x);
mn[o]=min(mn[ls],mn[rs]);
}
int ck(ll x){
build(1,1,n);
for(int i=1;i<k;i++){
ud(1,1,n,x);
if(mn[1]-i<0)return 0;
}
return 1;
}
int main(){
cin>>n>>k;
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
for(i=1;i<=n;i++){
scanf("%lld",&b[i]);
r=max(r,b[i]*k-a[i]);
}
if(!ck(r)){cout<<-1;return 0;}
while(l<r){
mid=(l+r)/2;
if(ck(mid))r=mid;
else l=mid+1;
}
cout<<l;
}