撰写时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 159 测试通过 : 24
比赛描述
oo终于回到家吃到了他最喜欢的汉堡包，他特别喜欢用自己做自己想要的汉堡包。oo认为汉堡包大体上有三种成分组成：面包、肉片、奶酪。于是他写了一份自己最爱吃的一种汉堡包的食谱，食谱中面包用B表示，肉片用M表示，奶酪用C表示。食谱中的成分从下到上，比如说BMCBM代表汉堡包，那就是说这个汉堡包从下到上分别用了面包、肉片、奶酪、面包、肉片。 现在oo有nb块面包，nm片肉片，nc块奶酪。他决定自己来做汉堡包来满足自己无止尽的食欲。由于食欲是无止尽的，所以他想到附近的商店去买一些面包、肉片和奶酪。 他现在有r块钱，面包、肉片、奶酪的价格为pb,pm,pc。 如果商店里每种成分都是无限的，那么oo最多能吃到多少个他想吃的汉堡包？
输入
第一行一个整数T，表示case的个数，对于每个case，第一行一个字符串，由BMC组成（题目保证字符串长度不超过100），表示oo喜欢的汉堡包的食谱，第二行三个整数nb,nm,nc，第三行三个整数pb,pm,pc，第四行一个整数r。 (1<=T<=10,1<=nb,nm,nc<=100,1<=pb,pm,pc<=100, 1<=r <= 10^12)
输出
每个case输出一个整数，表示答案。
样例输入
1
BBBMMC
6 4 1
1 2 3
4
样例输出
2
题解：应该可以先将一种按汉堡比例相对来说最小的食材满足第二大食材之间的比例为1：1，再将两个看作一种，和第一大的比例调成1：1，最后直接整个判断，中间过程需要判断钱是否用完，但是这种方法太过麻烦，不如直接用二分法，以金钱加上所有食材的初始数量作为r，进行二分，注意在二分过程中要注意初始食材以及二分的上下限取值（一般取左闭右开，相等时退出）。
/*
ID: oodt
PROG:
LANG:C++
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
const int maxx=1000500;
int n,m,k;
int a[maxx];
int ans = 0,cnt = 0,pos = 0;
long long l = 0,r = 0;
long long n1,n2,n3,s1,s2,s3,q;
long long b,M,c;
string s;
int check(long long mid){
long long nb,ns,nc;
nb = mid * b - n1;
if(nb < 0) nb = 0;//未达到初始量则不花钱
ns = mid * M - n2;
if(ns < 0) ns = 0;
nc = mid * c - n3;
if(nc < 0) nc = 0;
if(nb * s1 + ns * s2 + nc * s3 > q) return 0;
return 1;
}
char ss[maxx];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",ss);
string s = string(ss);
b = M = c = 0;
for(int i = 0; i < s.size(); i++)
{
if(s[i] == 'B') b++;
if(s[i] == 'M') M++;
if(s[i] == 'C') c++;
}
scanf("%I64d%I64d%I64d",&n1,&n2,&n3);
scanf("%I64d%I64d%I64d",&s1,&s2,&s3);
scanf("%I64d",&q);
l = 0;
r = n1+n2+n3+q;//因为可能是1或者其他的数，所以选择一个保证能二分到的上线
long long mid;
while(l < r){
mid = (l + r+1) / 2;
if(check(mid)){
l = mid;
}
else r = mid - 1;
}
printf("%I64d\n",l);
}
return 0;
}