GitBook

这里写图片描述 这里写图片描述

计算单位价值之后排序就好 需要注意若物品“免费” 则可以直接把其重量加入sum

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node {
	int j,f;
	double m;
} a[1200];
bool cmp(node A,node B) {
	return A.m>B.m;
}
int main() {
	int m,n;
	while(scanf("%d %d",&m,&n),m!=-1||n!=-1) {
		double sum=0;
		for(int i=0; i<n; i++) {
			scanf("%d %d",&a[i].j,&a[i].f);
			if(a[i].f>0)
				a[i].m=(double)a[i].j/a[i].f;
			else {
				a[i].m=0;
				sum+=a[i].j;
			}
		}
		sort(a,a+n,cmp);
		for(int i=0; i<n; i++) {
			sum+=min(m,a[i].f)*a[i].m;
			m-=min(m,a[i].f);
		}
		printf("%.3lf\n",sum);
	}
	return 0;
}

题目地址:【杭电】[1009]FatMouse’ Trade