PAT 1070

共计 645 个字符，预计需要花费 2 分钟才能阅读完成。

简单的贪心问题，和背包问题类似，这里不再赘述
#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].price*moc[i].num;
m-=moc[i].num;
}else{
money+=m*moc[i].price;
m=0;
}
}
printf(“%.2f\n”,money);
system(“pause”);
return 0;
}