【每日一题】9月29日题目精讲

看到就会想到要二分这个x的值，那么接下来就考虑如何check()这个这个x值.
考虑使用一个优先队列，按照可以撑的时间排序，每次给可以撑的时间最少的点加上x的电，然后每当有可以超过k的，就直接移出队列，当队列为空时，便为成功，然后继续二分即可.

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
//#include<bits/stdc++.h>
typedef long long ll;
#define INF 0x3f3f3f3f
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int maxn = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)        //快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
template <class T>//快读
void read(T& x)
{
    char c;
    bool op = 0;
    while (c = getchar(), c < '0' || c > '9')
        if (c == '-')
            op = 1;
    x = c - '0';
    while (c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if (op)
        x = -x;
}
template <class T>
void write(T x)
{
    if (x < 0)
        x = -x, putchar('-');
    if (x >= 10)
        write(x / 10);
    putchar('0' + x % 10);
}
///////////////////////////////////////////////////////////建图用的结构体
struct Edge
{
    int v, w, next;
}edge[maxn];
int tot = 0;
int head[maxn];
inline void Add_edge(int u, int v, int w)//建立邻接表
{
    edge[++tot].next = head[u];
    head[u] = tot;
    edge[tot].v = v;
    edge[tot].w = w;
}
///////////////////////////////////////////////////////////
ll a[maxn];
ll b[maxn];
ll n, k; 
struct node {
    ll a, b, c;
    bool operator < (const node& x)const {
        if (c != x.c)
            return c > x.c;
        if (b != x.b)
            return b < x.b;
        return a > x.a;
    }
};
priority_queue<node> q;
bool check(ll y) {
    while (!q.empty()) 
        q.pop();
    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++) {
        node t = q.top();
        q.pop();
        if (t.c < i)
            return false;
        if ((t.a + y) / t.b < k)
            q.push({ t.a + y,t.b,(t.a + y) / t.b });
        if (q.empty())
            return true;
    }
    return true;
}
int main() {
    read(n);
    read(k);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    for (int i = 1; i <= n; i++)
        read(b[i]);
    ll l = 0, r = 2e12;
    ll ans = -1;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (check(mid))//找最小值，所以找到符合条件的应该让r=mid-1
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}
/*
2 4
3 2
4 2
*/