2017-06-16 • 于二分答案贪心阅读

汉堡

贪心的方法做，现找出用原始材料能做的汉堡，在对多出来的材料进行贪心，把少的用钱买上，如果没钱了，就输出，如果有钱就没有多出来的了，可以直接买了

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
char a[9999999]; ll t;int b,s,c,nb,ns,nc,qb,qs,qc;
int main(){
	cin>>a;
		for(int i=0;i<strlen(a);i++)
	{
		if(a[i]=='B')
		nb++;
		if(a[i]=='S')
		ns++;
		if(a[i]=='C')
		nc++;
	}//找一个汉堡里的材料
	scanf("%d%d%d%d%d%d%I64d",&b,&s,&c,&qb,&qs,&qc,&t);
	ll ans=min(nb?(b/nb):12e+101,min((nc?(c/nc):12e+101),ns?(s/ns):12e+101));//找原材料能造的汉堡
	b-=nb*ans;
	c-=nc*ans;
	s-=ns*ans;
	ll w=nb*qb+nc*qc+ns*qs;
	while((b&&nb)||(c&&nc)||(s&&ns)){
		
		if(b<nb)
		{
			t-=(nb-b)*qb;
			b=0;	
		}
		else b-=nb;
		if(c<nc)
		{
			t-=(nc-c)*qc;	
			c=0;
		}
		else c-=nc;
		if(s<ns)
		{
			t-=(ns-s)*qs;
			s=0;	
		}
		else s-=ns;
		if(t<0) break;
		ans++;
	}//把多的材料用掉
	printf("%I64d",ans+t/w);//输出汉堡书
}

对汉堡进行二分答案，如果花的钱多了就买少点，少了就买多点

#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
char a[9999999]; ll r,l,t;int b,s,c,nb,ns,nc,qb,qs,qc;
bool check(ll x){
	ll money=0;
	if(b<x*nb) money+=(x*nb-b)*qb;
	if(c<x*nc) money+=(x*nc-c)*qc;
	if(s<x*ns) money+=(x*ns-s)*qs;
	return money<=t;
}
int main(){
	cin>>a;
		for(int i=0;i<strlen(a);i++)
	{
		if(a[i]=='B')
		nb++;
		if(a[i]=='S')
		ns++;
		if(a[i]=='C')
		nc++;
	}
	scanf("%d%d%d%d%d%d%I64d",&b,&s,&c,&qb,&qs,&qc,&t);

	r=1e12+101;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	printf("%I64d",r);
}

wspl09876

汉堡

FoxDividingCheesecodeforces371b

聪明的质检员