読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

Codeforces Round #350 (Div. 2) D1,D2. Magic Powder

問題
Problem - D1 - Codeforces
クッキーを作ろうとしている.1つ作るのにN種類の材料がA_iずつ必要である.初めにB_iずつ持っているとする.また,Kのマジックパウダーも持っており,そのパウダーはどの材料にも変えることができる.作れるクッキーの最大値はいくつか.

制約
D1: 1\leq N,K\leq1000,1\leq A_i,B_i\leq1000
D2: 1\leq N\leq100000,1\leq K\leq10^9,1\leq A_i,B_i\leq10^9

解法
作れるクッキーの最大値は多くても2\cdot10^9なので,クッキーの数を[1,2\cdot10^9]で二分探索する.
クッキーの数を決めてしまえば,必要な材料の数も決まるので足りない分だけKから引いていき,Kが0を下回るかどうかで二分探索の方向を決める.Kがマイナスにオーバーフローしないように気をつける.
計算量はO(N\log10^9)

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,(int)(n)-1,0)
#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define INF 100000000

typedef long long ll;

int main() {
    int i, n, k;
    ll l, r;
    int a[100000], b[100000];
    scanf("%d%d",&n,&k);
    rep (i,n) scanf("%d",a+i);
    rep (i,n) scanf("%d",b+i);
    l = 0; r = 2e9+1;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        ll rest = k;
        rep (i,n) {
            if (a[i]*m > b[i])
                rest -= a[i]*m - b[i];
            if (rest < 0)
                break;
        }
        if (rest >= 0)
            l = m;
        else
            r = m;
    }
    printf("%d\n",(int)l);
    return 0;
}