CF1132D Stressful Training（優先隊列+二分）

看到就會想到要二分這個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
*/
           

很經典的二分用法，得需要牢記