二分答案：Poweroj2461-入门基础之二分答案(二分法的应用)

入门基础之二分答案

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 179 Accepted: 33 Page View: 744

Description

M78喜欢积木，更喜欢机器人。于是，他决定用积木组装机器人。积木总共有三种，做一个机器人需要三种类型的积木分别a，b，c个。现在，他分别有这三种积木x，y，z个。另外，他还有一些金币。他总共有sum个金币，他可以用这些金币购买积木，购买这三种积木分别会花费c1，c2，c3金币。M78想尽可能地多做一些机器人，问，他最多能做多少个机器人？

Input

多组输入。每组输入共三排。
第一排，三个整数a，b，c。(1<=a,b,c<=100)
第二排，三个整数x，y，z。(0<=x,y,z<=100)
第三排，四个整数sum，c1，c2，c3。(0<=sum<=10^12,1<=c1,c2,c3<=100)
符号的意义同题目描述中一样。

Output

对于每组，输出一排，这排只有一个整数，表示M78能组装的最多的机器人数。

Sample Input

1 2 3
100 100 100
300 7 8 9

Sample Output

解题心得

1、写这个博客的时候还是大一，写的很烂，后来看到很多学弟来看就把这个博客重新写了一遍。

2、这个题做法是二分答案，那么什么是二分答案呢，其实就是二分枚举出答案，然后将答案给带入题意中去检验，如果检验出来枚举的答案大了，那么就将这个答案二分减小，小了就二分变大。

#include <algorithm>

#include <stdio.h>

using namespace std;

long long x,y,z,a,b,c,sum,c1,c2,c3;

bool check(long long cnt) {

    long long need_a = cnt*a;

    long long need_b = cnt*b;

    long long need_c = cnt*c;

    long long need_money = 0;

    need_money = max((long long)0,need_a - x)*c1 + max((long long)0,need_b-y)*c2 + max((long long)0,need_c-z)*c3;//要制作cnt个机器人将材料用完还需要使用的钱

    if(need_money > sum)//如果需要使用的钱比当前的钱更大那么不符合条件，二分缩小

        return true;

    return false;

}

long long binary_search() {

    long long l = 0, r = 1e12, mid;

    while(r - l > 1) {//闭区间是取在ｌ的所以返回的是ｌ

        mid = (l+r)/2;//mid = (l+r)>>1;

        if(check(mid))

            r = mid;

        else

            l = mid;

    }

    return l;

}

int main() {

    while(scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&x,&y,&z,&sum,&c1,&c2,&c3) != EOF) {

        long long ans = binary_search();

        printf("%lld\n", ans);

    }

    return 0;

}

秒客网