Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

@acerols

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;
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
0
Help us understand the problem. What are the problem?