题意
\(n\) 个电脑，需要保证其在时刻 \(1\) 至 \(k\) 的电量为正。初始电量为 \(a_i\)，每时刻消耗 \(b_i\)。
有一个电源，每一时刻可以给一个电脑充电，使其消耗变为 \(b_i-x\)（可以为负）。
求电源的最小功率，无解输出 \(-1\)。
\(1\leq n,k \leq 2\times 10^5\)，\(1\leq a_i \leq 10^{12}\)，\(1\leq b_i \leq 10^7\)。
题解
很容易想到二分。
check也很简单，每一时刻给最快没电的电脑充电，可以用数据结构维护。如果这一时刻电量为负，说明无解。
实测用线段树会TLE，用优先队列稍加卡常就能过。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
struct computer
{int a,b;int left,last;
}a[Maxn];
int n,k;
bool operator<(computer x,computer y)
{return (__int128)x.a*y.b>(__int128)y.a*x.b;
}
bool check(int x)
{priority_queue<computer>q;for(int i=1;i<=n;i++) q.push(a[i]);for(int i=1;i<=k;i++){computer tmp=q.top();q.pop();if(tmp.a<(i-1)*tmp.b) return 0;tmp.a+=x;q.push(tmp);}return 1;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i].a;for(int i=1;i<=n;i++) cin>>a[i].b;int l,r,mid,ans=-1;l=0,r=2e12;while(l<=r){mid=(l+r)>>1;if(check(mid)) ans=mid,r=mid-1;else l=mid+1;}cout<<ans<<endl;return 0;
}