2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

AtCoder ABC 144 E Gluttony

Posted at

# AtCoder YouTubeの言語化
https://www.youtube.com/watch?v=JYLI4mZH-p8&t=3074s
# 問題

考え方

食べ物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;
}
2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?