PAT L2-003. 月饼

题意：

给你每种月饼库存和销售全部这种月饼能得到的钱，问在需要k吨月饼的情况下，最大的收益

题解：

贪心一下，注意的是价格是实数

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=1e4+7;
 6 struct Node
 7 {
 8     double a,b,f;
 9     bool operator<(const Node &b)const{return f>b.f;}
10 }a[N];
11 int n,need;
12 
13 int main()
14 {
15     scanf("%d%d",&n,&need);
16     F(i,1,n)scanf("%lf",&a[i].a);
17     F(i,1,n)scanf("%lf",&a[i].b),a[i].f=1.0*a[i].b/a[i].a;
18     sort(a+1,a+1+n);
19     double ans=0;
20     F(i,1,n)
21     {
22         if(a[i].a<=need)
23         {
24             ans+=a[i].b;
25             need-=a[i].a;
26         }else
27         {
28             ans+=need*a[i].f;
29             need=0;
30         }
31     }
32     printf("%.2f
",ans);
33     return 0;
34 }

View Code