题目大意:你经营着一个柠檬水摊,很幸运地知道你经营柠檬水摊的每一天顾客会想买多少杯柠檬水。你讨厌拒绝任何顾客,所以你想确保你每天总是有足够的柠檬和糖来制作适当数量的柠檬水。不幸的是,柠檬和糖的价格每天都在变化,所以你必须选择在哪一天买,买多少。你可以买单个柠檬和五磅袋糖。(请注意,一磅有 16 盎司。)在你选择购买配料的日子里,你会在早上,在任何销售之前购买配料。(你是一个早起的人,所以你总是可以在任何顾客来之前到达商店并回来。)请注意,你可以在任何一天购买尽可能少或尽可能多的东西来最小化你的总成本,也就是说,你有足够的启动资金 (资本) 在任何一天,你想买多少就买多少。
这是个贪心题,还是比较简单的但是当时想的思路很乱,(写的也很乱)很难改;所以很难找出错在哪,看了一会就放弃了,现在再回来看还是比较简单的,所以痛定思痛要把代码格式写好,真的很重要;
本题思路就是找局部最小的价格作为当天的价格,特别说明糖是按袋卖的,所以要判断买几袋或者是不买;
上代码
(AC代码)
#include<bits/stdc++.h> using namespace std; struct mp{ int day; int lem; int tang; }p[10000]; int main(){ int t; cin>>t; while(t--) { int m,i,j,p1,p2,num=0,ans=0; cin>>m>>p1>>p2; int minl=1e9,mint=1e9; for(i=1;i<=m;i++) { scanf("%d%d%d",&p[i].day,&p[i].lem,&p[i].tang); } for(i=1;i<=m;i++) { int dai=0; if(p[i].lem<minl)minl=p[i].lem; if(p[i].tang<mint)mint=p[i].tang; ans+=p[i].day*minl*p1; if(num<p[i].day*p2){ dai=(p[i].day*p2-num)/80; num=(p[i].day*p2-num)%80; if(num!=0) { dai++; num=80-num; } }else num=num-p[i].day*p2; ans+=dai*mint; } cout<<ans; if(t!=0)cout<<endl; } }
原始代码(里面有好多bug,确实看不出来了qwq)
#include<bits/stdc++.h> using namespace std; struct money{ int day; int lem; int tang; }p[10000]; int main(){ int t; cin>>t; while(t--){ int m,i,j,p1,p2; cin>>m>>p1>>p2; for(i=1;i<=m;i++){ scanf("%d%d%d",&p[i].day,&p[i].lem,&p[i].tang); } int num1=0,num2=0,ans=0,v=0,q=0; for(i=1;i<=m;i++){ v=0; for(j=i;j<=m;j++){ if(p[i].lem<=p[j].lem){ v=v+p[j].day; } else { break; } } // cout<<v<<endl; num1+=p[i].lem*v*p1; i=j; // cout<<i<<" "<<j<<endl; // cout<<num1<<" "<<p1<<endl; } int now=0,dai; for(i=1;i<=m;i++){ dai=0; v=0,q=0; for(j=i;j<=m;j++){ if(p[i].tang<=p[j].tang){ v=v+p[j].day; } else{ break; } } // cout<<j<<endl; if(now>=p2*v){ now=now-p2*v; dai=0; } else{ dai=(v*p2-now)/80; now=(v*p2-now)%80; if(now!=0)dai=dai+1; } num2+=p[i].tang*dai; // cout<<dai<<" "<<p[i].tang<<" "<<now<<endl; i=j; cout<<i<<" "<<m<<endl; } cout<<i<<endl; cout<<num1+num2; if(t!=0)cout<<endl; cout<<num1<<" "<<num2; } }