2832_生日宴会_二分

lzusa 发布于 2017-11-07 1 次阅读

题目描述

Alice在餐馆里当服务员，今天是她生日，她请求厨师帮她准备生日晚餐，晚餐由N种原料做成，每道菜所需每种原料的数量是一样的。 
　　厨房里有一些原料，但不够，Alice还需要从旁边的超市中购买一些回来。超市里什么原料都有，每种原料都分大包装和小包装。Alice有M元钱，她想利用这M元钱购买原料使得能做出最多的菜。

思路

我们可以二分一个能做出的菜的数量，然后通过暴力判断出能否即可

#include 
#define N 101
#define INF 0x7f7f7f7f
#define min(x, y) ((x) < (y) ? (x) : (y))
int n, m;
struct arr
{
    int x, y, sm, pm, sv, pv;
}a[N];
int check(int mid)
{
    int ttt = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = a[i].x * mid - a[i].y;
        if (t <= 0) continue;
        int tot = INF;
        int j;
        for (j = 0; a[i].sm * j <= t; j++)
        {
            int l = t - a[i].sm * j;
            int r = l / a[i].sv;
            if (l > r * a[i].sv) r++;
            tot = min(tot, j * a[i].pm + r * a[i].pv);
        }
        j = t / a[i].sm;
        if (t > j * a[i].sm) j++;
        tot = min(tot, j * a[i].pm);
        j = t / a[i].sv;
        if (t > j * a[i].sv) j++;
        tot = min(tot, j * a[i].pv);
        if (tot == INF) return 0;
        if (tot != INF) ttt += tot;
        if (ttt > m) return 0;
    }
    return 1;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d%d%d%d", &a[i].x, &a[i].y, &a[i].sm, &a[i].pm, &a[i].sv, &a[i].pv);
    int l = 0, r = 100100;
    int ans = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    printf("%d\n", ans);
}

 

]]>