ハンバーグ
6328 ワード
欲張りな方法で作って、今原始材料で作れるハンバーガーを見つけて、多くの材料に欲張りをして、少ないお金を買って、お金がなければ、出力して、お金があれば多く出てこないので、直接買うことができます
ハンバーガーに対して2点の解答を行って、もし使うお金が多くなったら少なく買って、少なくなったら多く買います
#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);//
}
ハンバーガーに対して2点の解答を行って、もし使うお金が多くなったら少なく買って、少なくなったら多く買います
#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);
}