atcoder beginner contest 144 Gluttony（二分答案）

题目大意：

有an,bn ，我们找到an和bn每个元素的一种一一对应关系。使得min( max(ai*bi))。

已知我们可以进行操作让an中的任一个元素减少1。操作数最大为k，问我们怎么操作，可以min( max(ai*bi))。

解题思路：

首先，我们一个很直接的发现是：让an和bn进行一个排序，让an从小到大让bn从大到小排序，这时候让它们上下对齐放好，它们上下连线即为一个最佳匹配。em 证明..... 不懂。但是这样的确是最优匹配。因为很直观的发现，我们不想让ai和bi中大的放在一起，尽量让他们和对面的小的进行匹配。这时候，进入最关键的一步，枚举答案！

这里我们二分枚举答案。 这是本题最重要的思路！这里，为什么想到二分呢？首先，我们要想到枚举答案这个思路。其次我们试一下暴力枚举，但是暴力枚举在这里会超时，我们尝试二分枚举。每次得到一个答案，我们扫一遍数列，需要多大的操作数，若是小于k，我们则把答案继续缩，若是比k大，我们则把答案往大的扩。

二分的左边界是0，右边界是max(ai*bi)

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> a;
vector<int> b;
int32_t main(){
  int n,k;cin>>n>>k;
  for(int i=0;i<n;i++){
    int t;cin>>t;
    a.push_back(t);
  }
  for(int i=0;i<n;i++){
    int t;cin>>t;
    b.push_back(t);
  }
  sort(a.begin(),a.end(),less<int>());
  sort(b.begin(),b.end(),greater<int>());
  int y=-1;
  for(int i=0;i<n;i++){
    y=max(a[i]*b[i],y);
  }
  int x=0;
  int time=0;
  while(x<y){
    int m=x+(y-x)/2;
    int suc=1;
    int tmpk=0;
    time++;
    cerr<<"mid "<<m<<endl;
    cerr<<time<<endl;
    for(int i=0;i<n;i++){
      int res=m/b[i];
      //cerr<<i<<" "<<res<<endl;
      if(res>a[i])continue;
      tmpk+=a[i]-res;
      //cerr<<tmpk<<endl;
      if(tmpk>k){
      suc=0;
      break;}
    }
    if(suc)y=m;
    else x=m+1;
  }
  assert(x==y);
  cout<<x<<endl;
  
  return 0;
}