PAT 1070

简单的贪心问题，和背包问题类似，这里不再赘述#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<cmath>#include<algorithm>using namespace std;using std::vector;const int maxn=1010;struct node{ double num; double price;};bool cmp(node a,node b){ return a.price>b.price;}node moc[maxn];int n;double m;int main(){ double p; scanf("%d%lf",&n,&m); for(int i=0;i<n;i++){ scanf("%lf",&moc[i].num); } for(int i=0;i<n;i++){ scanf("%lf",&p); moc[i].price=p/moc[i].num; } sort(moc,moc+n,cmp); double money=0; for(int i=0;i<n;i++){ if(m==0) break; if(moc[i].num<=m){ money+=moc[i].pricemoc[i].num; m-=moc[i].num; }else{ money+=mmoc[i].price; m=0; } } printf("%.2f\n",money); system(“pause”); return 0;}