codeforces 371 C-Hamburgers

一个乱七八糟的故事背景，可以练练英语阅读。

大概的意思是Polycarpus喜欢汉堡，现在他有你ns片香肠片，nb面包，nc块起司，有r卢布，每种东西都有价格，如果不够他可以去商店买（商店里面各种东西都是无限多的），制作汉堡需要多少各种东西都已经用字符串给出了，求他最多可以制作出多少汉堡。

简单二分，主意的是二分的上界，可能会超过10^12,就因为这个WA了两次。

#include <stdio.h>

#include <string.h>

#define maxn 2000000000000

#define ll long long

#include <iostream>

using namespace std;

int cntb, cnts, cntc;

int nb, ns, nc;

int pb, ps, pc;

ll r;

char str[105];

ll cal(ll x)

{

    ll sum = 0;

    if (x*cntb - nb > 0)

        sum += (x*cntb - nb) * pb;

    if (x*cntc - nc > 0)

        sum += (x*cntc - nc) * pc;

    if (x*cnts - ns > 0)

        sum += (x*cnts - ns) * ps;

    return sum;

}

ll binarysearch(ll l, ll r, ll x)

{

    //cout << l << " " << r << " " << x << endl;

    if (l == r)

    {

        while (cal(l) > x)

            l--;

        return l;

    }

    ll mid = (l+r)>>1;

    if (cal(mid) > x)

        return binarysearch(l, mid, x);

    else

        return binarysearch(mid+1, r, x);

}

int main()

{

    while (scanf("%s", str) != EOF)

    {

        int len = strlen(str);

        cntb = 0, cnts = 0, cntc = 0;

        for (int i = 0; i < len; i++)

        {

            if (str[i] == 'B')

                cntb++;

            else if (str[i] == 'S')

                cnts++;

            else if (str[i] == 'C')

                cntc++;

        }

        scanf("%d %d %d", &nb, &ns, &nc);

        scanf("%d %d %d", &pb, &ps, &pc);

        cin >> r;

        cout << binarysearch(0, maxn, (ll)r) << endl;

    }

    return 0;

}

巴特西

codeforces 371 C-Hamburgers

最新文章

热门文章