1070 Mooncake （25 分）

Mooncake （25 分）"/>

1070 Mooncake （25 分）

这道题是我接触得最早得贪心算法题，但是没想到这次做还是有个测试点没过去。
主要是样例给得数据让我主观得认为，总量一定是整数。
然后我反复得读题目，似乎也没发现这里隐藏得陷阱。
出题人这样搞我们真的不怕下雨天被雷带走吗？

版本1

PAT测试点

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e3+5;
struct cake{double price,per,amount;
}C[maxn];
bool cmp(cake a, cake b){return a.per > b.per;
}
int main(){int n;double m;scanf("%d%lf",&n,&m);for(int i=0;i<n;i++){scanf("%lf",&C[i].amount);}for(int i=0;i<n;i++){scanf("%lf",&C[i].price);C[i].per = C[i].price/C[i].amount;}sort(C,C+n,cmp);double ans=0.0;for(int i=0;i<n;i++){if(m > C[i].amount){ans += C[i].price;m -= C[i].amount;}else {ans += m * C[i].per;break;}}printf("%.2f\n",ans);return 0;
}

版本2

牛客网测试点

#include<bits/stdc++.h>
using namespace std;
struct cake{double amounts, price, single;
}E[1010];
bool cmp(cake a, cake b){return a.single > b.single;
}
int main(){int n;double d, t;cin >> n >> d;for(int i = 0; i < n; i++){cin >> t;E[i].amounts = t;}for(int i = 0; i < n; i++){cin >> t;E[i].price = t;E[i].single = t/E[i].amounts;}sort(E, E + n, cmp);double ans = 0;for(int i = 0; i < n; i++){if(d >= E[i].amounts){ans += E[i].price;d -= E[i].amounts;}else{ans += E[i].single * d;break;}}printf("%.2f\n", ans);return 0;
}