CF1132D Streessful Training(二分+贪心+优先队列*2300)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
typedef long long ll;
using namespace std;
const int N = 3e5 + 10;
ll n, k;
ll a[N], b[N];
struct node {
  ll a;
  ll b;
  ll c;
  bool operator<(const node &w)const {
    return c > w.c;  //从堆底到根 从大到小 即 小根堆
  }
};
bool check(ll x) {
  priority_queue<node>q;
  for (int i = 1; i <= n; i++) {
    if (a[i] / b[i] < k)
      q.push({a[i], b[i], a[i] / b[i]});
  }
  if (q.empty()) return true;
  for (int i = 0; i < k; i++) {
    auto t = q.top();
    q.pop();
    if (t.c < i) return false;
    if ((t.a + x) / t.b  < k) {
      q.push({t.a + x, t.b, (t.a + x) / t.b });
    }
    if (q.empty()) return true;
  }
  return true;
}
int main() {
  scanf("%lld%lld", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);
  //枚举最小答案
  ll l = 0, r = 3e12 + 10;
  bool f = 0;
  while (l < r) {
    ll mid = l + r >> 1;
    if (check(mid)) {
      r = mid;
      f = 1;
    } else l = mid + 1;
  }
  if (f == 1)
    cout << l << "\n";
  else cout << -1 << "\n";
  return  0;
}