Hamburgers（二分）

题目：Hamburgers

vjudge提交链接

题意：

亲手做汉堡
第1行：给出一个字符串，代表汉堡，只由字母B，S，C组成，
第2行：给出字母B，S，C现有数量
第3行：给出字母B，S，C的单价
第4行：给出手中的金钱总数。

求：最多能做出多少汉堡。

附上本人参考的博文：
紫芝
-白羊-

解题思路：

1. 暴力求解很难办，因为钱分配问题比较难处理。
2. 二分枚举做出来的汉堡数量，从而可得每个类型所需的材料数量，当然必须减去手中原有的材料数量。计算出所需材料总费用，最后与金钱总数比较，不断放缩区间，最终得最大汉堡数量。
3. 二分求mid本人习惯于用mid=high-(high-low)/2，这样求的mid中间偏右，而mid=(low+high)/2;，求的mid中间偏左。做题用哪个都行，只是在输出时要格外注意些。

代码：

#include
#include
#include
using namespace std;
typedef long long ll;
const ll Maxn=1e12+110;
char a[1100]; 
int tb,ts,tc;
int nb,ns,nc;
int pb,ps,pc;
ll Mo;
int check(ll x)
{ll d=0;//t1,t2,t3分别表示做出x个汉堡需要的B，S，C的数量，该值不能为负数。 ll t1=max(tb*x-nb,d);ll t2=max(ts*x-ns,d);ll t3=max(tc*x-nc,d);if(t1*pb+t2*ps+t3*pc<=Mo)return 1;elsereturn 0;
}
int main()
{tb=0,ts=0,tc=0;int i,la;scanf("%s",a+1);la=strlen(a+1);scanf("%d %d %d",&nb,&ns,&nc);scanf("%d %d %d",&pb,&ps,&pc);scanf("%lld",&Mo);for(i=1;i<=la;i++){if(a[i]=='B')tb++;if(a[i]=='S')ts++;if(a[i]=='C')tc++; }//二分求最大汉堡数量，这里输出high ll low=0,high=Maxn,mid;while(low<=high){mid=high-(high-low)/2;if(check(mid)==1)low=mid+1;elsehigh=mid-1;}printf("%lld\n",high);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！