[PAT解题报告] Mooncake
简单题，给定月饼的种类和市场总需求量，再给定每种月饼的重量和售价（这些重量的价钱），求最多能卖多少钱——每种月饼可以卖任意数量，得到的钱就是那个售价的比例。
分析：
著名的0-1背包问题，可以取一部分。可以简单地证明，肯定优先取“性价比”最高地，这里“性价比”指的是单位重量的售价。因为如果我们不取“更贵”的，我们可以用更贵的换掉便宜的，从而获得更大的收益。
所以就变成简单的贪心了，把月饼按单位重量售价由高到低排序，当然我是用乘法代替的除法，不过因为都是浮点数，可能直接用除法问题也不大。
然后就从最贵的开始选了，装满要的市场量为止——或者所有都取完了，仍然没达到市场需求。
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
pair<double,double> a[1024];
const double eps = 1.e-8;
bool cmp(const pair<double,double> &a, const pair<double,double> &b) {
return a.second * b.first > b.second * a.first;
}
int main() {
int n;
double m;
scanf("%d%lf",&n,&m);
for (int i = 0; i < n; ++i) {
scanf("%lf",&a[i].first);
}
for (int i = 0; i < n; ++i) {
scanf("%lf", &a[i].second);
}
sort(a, a + n, cmp);
double answer = 0.;
for (int i = 0; i < n; ++i) {
if (a[i].first + eps <= m) {
answer += a[i].second;
m -= a[i].first;
}
else {
answer += m * a[i].second / a[i].first;
break;
}
}
printf("%.2lf\n",answer);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1070
投递阿里巴巴等公司10个岗位 >
中国联通工作强度 57人发布