【PAT甲级】1070 Mooncake (25 分)(贪心水中水)

题意:

输入两个正整数N和M(存疑M是否为整数,N<=1000,M<=500)表示月饼的种数和市场对于月饼的最大需求,接着输入N个正整数表示某种月饼的库存,再输入N个正数表示某种月饼库存全部出手的利润。输出最大利润。

trick:

测试点2可能包含M不为整数的数据。(尽管题面说明M是正整数,可是根据从前PAT甲级题目的经验,有可能不是整数。。。。。)

AAAAAccepted code:

 #define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
double a[];
double b[];
pair<double,int>p[];
int main(){
int n;
double m;
scanf("%d%lf",&n,&m);
for(int i=;i<=n;++i)
scanf("%lf",&a[i]);
for(int i=;i<=n;++i)
scanf("%lf",&b[i]);
for(int i=;i<=n;++i)
p[i].first=b[i]/a[i],p[i].second=i;
sort(p+,p++n);
double sum=;
double ans=;
for(int i=n;i;--i)
if(sum+a[p[i].second]<=m){
sum+=a[p[i].second];
ans+=b[p[i].second];
}
else{
ans+=(m-sum)*p[i].first;
break;
}
printf("%.2f",ans);
return ;
}
上一篇:Maven学习


下一篇:Zuul过滤器