B. 买米 Problem ID: 3688 Contest ID: 4303 选做题

常规
, ,
1

#include
#include
using namespace std;
struct rice{
int a,b;
}r[5005];
bool cmp(rice a,rice b){
return a.b<b.b;
}
int n,s,x,sum;
int main(){
cin>>n>>s;
for(int i=0;i<n;i++){
cin>>r[i].a>>r[i].b;
}
sort(r,r+n,cmp);
for(int i=0;i<n;i++){
if(s>=r[i].ar[i].b){
s-=r[i].ar[i].b;
sum+=r[i].a;
}
else{
x=s/r[i].b;
s-=x*r[i].b;
sum+=x;
}
}
cout<<sum;
return 0;
}

1 个赞
2

这题主要考查的是贪心，要尽量买性价比最高的米，需要对米的重量和单价进行排序：

for(int i=1;i<n;i++)
{
    for(int j=1;j<=n-i;j++)
    {
        if(b[j]>b[j+1])
        {
            swap(b[j],b[j+1]);
            swap(a[j],a[j+1]);
        }
    }
}

然后一边判断钱有没有用完，一边累加斤数和减少钱数：

for(int i=1;i<=n;)
{
    while(s>=b[i] && a[i]>0)
    {
    	a[i]--;
    	sum++;
    	s=s-b[i];
    }
	i++;
}
cout<<sum<<endl;
2 个赞