分析

比较简单的贪心题。我们考虑到二分一个答案 。那么存在 也是成立的。所以这个是具有单调性的。那么为了让所有的点都是合法的。那么肯定要拿出最近一个将要不合法的节点让他的电量 。那么当第 次充电时发现最近的节点没电的时间在 之前，则是个非法答案。那么我们算法就是如果快速找到第一个将要不合法的点。这里考虑用 来维护就好了。那么总的复杂度为 。

• 还有一些减枝的小技巧，就看代码了。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const LL N = 2e5 + 100;
struct Node{
    LL a,b,c;
    bool operator <(const Node T) const {
        if(c ^ T.c) return c > T.c;
        else if(b ^ T.b) return b < T.b;
        return a > T.a;
    }
};
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
LL n,m,a[N],b[N];
bool check(LL mid) {
    priority_queue<Node> Q;
    for(LL i = 1;i <= n;i++) {
        if(a[i] / b[i] < m) Q.push((Node){a[i],b[i],a[i]/b[i]}); 
    }
    if(Q.empty()) return true;
    for(LL i = 0;i < m;i++) {
        Node x = Q.top();Q.pop();
        if(x.c < i) return false;
        if((x.a + mid) / x.b < m) Q.push((Node){x.a + mid,x.b,(x.a + mid)/x.b});
        if(Q.empty()) return true;
    }
    return true;
}
int main() {
    n = read();m = read();
    for(LL i = 1;i <= n;i++) a[i] = read();
    for(LL i = 1;i <= n;i++) b[i] = read();
    LL l = 0,r = 2e12,ans = -1;
    while(l <= r) {
        LL mid = l + r >> 1;
        if(check(mid)) ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    printf("%lld\n",ans);
    return 0;
}