AtCoder ABC 144 E Gluttony

　AtCoder YouTubeの言語化

　問題

考え方

食べ物F 消化コストF
前処理　消化コストを昇順、食べ物を降順にソート
1 とりえる最長時間と最短時間の真ん中が最短時間とおく。（最短時間をl, 最長時間をrとして、仮の最短時間をCとする。）
2 次にその時間でそれぞれの人間が食事したとして、それぞれの人間の消化コストを求める。この時消化コストが0以下の時は0とする。 $$ a'_i =C/F_i
\quad or\quad0$$
3 そしてもともとの消化コストから仮の最短時間での消化コストを引いたものの和をとる。$$\sum a_i - (C/F_i) $$
4 その和がKを超えればCは最短時間として更新する(l = c)。超えなければ最長時間として更新する(r = c)。
5 1-3を繰り返し二分探索で最短時間を求める。
　(最短時間+1) = (最長時間)となった時の最長時間が修行回数がKを超えない範囲での最短時間となる。

　回答

#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int main(void){
    // Your code here!
    int n;
    ll k; 
    cin >> n >> k;
    vector<int> a(n);
    vector<int> f(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> f[i];
    sort(a.begin(), a.end());
    sort(f.rbegin(), f.rend());
    ll l = -1, r = 1e12;
    while(l+1 < r){
        ll c = (l+r) / 2;
        ll sum = 0;
        rep(i,n)sum += max(0ll, (a[i] - c/f[i]));
        if(sum <= k)r = c;
        else l = c;
    }
    cout << r << endl;
}