CodeForces 371C Hamburgers（经典）【二分答案】

<题目链接>

题目大意：

给以一段字符串，其中只包含"BSC"这三个字符，现在有一定量免费的'B','S','C‘，然后如果想再买这三个字符，就要付出相应的价格。现在总共有tot元，问你最多能够组成几个这样的字符串。

解题分析：

开始还以为是模拟，但是看到总价的范围，达到了1e12,并且模拟的情况非常复杂。最后用二分答案求解。

 

#include <cstdio>
#include <cstring> 
using namespace std;

typedef long long ll;
const ll maxn = 1e12+100;    //本题二分答案的上界 
char str[110];
int base[4],price[4],ned[4];
ll tot;

bool juge(ll x) {     //判断是否能够买这么多汉堡，即验证二分答案的正确性 
	ll sum = 0;
	for (int i = 1; i <=3; i++) {
		if (base[i] < x*ned[i]) {
			sum += (price[i] * (x*ned[i] - base[i]));
			if(sum>tot)return false;
		}
	}
	return true;
}

ll binary_ans() {
	ll l = 0, r = maxn;
	while (l <= r) {
		ll mid = (l + r)/2;
		if (juge(mid))l = mid+1;
		else r = mid - 1;
	}
	return l-1;      //因为最后是l=mid+1跳出，而我们想要mid的值，所以这里是l-1 
}

int main() {
		scanf("%s",str); 
		memset(ned, 0, sizeof(ned));
		for (int i = 0; i < strlen(str); i++) {
			if (str[i] == 'B')ned[1]++;
			if (str[i] == 'S')ned[2]++;
			if (str[i] == 'C')ned[3]++;
		}
		for (int i = 1; i <= 3; i++)
			scanf("%d", &base[i]);
		for (int i = 1; i <= 3; i++)
			scanf("%d", &price[i]);
		scanf("%lld", &tot);
		printf("%lld\n", binary_ans());
	return 0;
}

 

 

2018-09-19