ハンバーグ

6328 ワード

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