题目描述

第一行输入共有N个同学，带了N个笔记本，N < 2e5 + 1，需要坚持 K 分钟。
第二行给出N个整数，每个整数代表笔记本初始电量，a[i] < 1e12 + 1
第三行给出N个整数，每个整数代表笔记本每分钟消好电量，b[i] < 1e7 + 1
现在你可以买一个充电器，再每分钟给某个笔记本充电 x 的电量，这个 x 最小是多少？如果永远无法满足那就输出 -1

Solution

稍微思考，可以发现这个答案 x 满足二分的性质，如果当前x可以，我是不是能买小一点的充电器呢？如果不行的就只能吧 x 变大了，所以可以二分这个答案去验证是否可以实现。
那么问题来到如何验证当前 x 是否可以使得全部机子活过 K 分钟。
那么每分钟充电一定是选坚持轮数最小的那一台机器，那么我们使用一个最小堆，把全部的需要充电才能活下来的机器放在最小堆里面去，最小堆的排序规则就是 越早死的排在越前面充电。
这个时候可以特判一下，如果堆中没有元素说明全部机子都可以活下来，不需要充电器，也就是当前 mid 可成立
在接下来枚举 k 分钟，每分钟选最小的机子充电，如果当前选出来的机器活不下来，那就是当前的充电器不合格。
再把充电之后的这个机器算一次可以活下多久，如果活不到 K 分钟就再塞进堆中，
循环 k 次过程中堆中再次没有元素了就还是 return true
完成 K 次循环也是返回 true

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<ll, pair<ll, ll> >
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 2e5 + 7;
ll n, k, a[N], b[N];

bool check(ll x) {
    priority_queue<pai, vector<pai>, greater<pai>> pq;
    for (int i = 1; i <= n; ++i)
        if (a[i] / b[i] < k)
            pq.push({ a[i] / b[i],{a[i],b[i]} });
    if (pq.empty())    return true;
    for (int i = 0; i < k; ++i) {
        ll C = pq.top().first, A = pq.top().second.first, B = pq.top().second.second;    pq.pop();
        if (C < i)    return false;
        if (A / B < k) {
            A += x;
            pq.push({ A / B,{A,B} });
        }
        if (pq.empty())    return true;
    }
    return true;
}

int main() {
    n = read(), k = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i <= n; ++i)
        b[i] = read();
    ll l = 0, r = 1e13, ans = -1;
    while (l <= r) {
        ll mid = l + r >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    print(ans);
    return 0;
}