GitBook

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

本来想着运用动态规划 不过这一题直接排序貌似更简单…… 还有白书上的那个背包问题 貌似也可以直接排序来解决

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node {
	int p,m;
} a[120];
bool vs(node A,node B) {
	return A.p>B.p;
}
int main() {
	int v;
	while(scanf("%d",&v),v) {
		int n;
		scanf("%d",&n);
		for(int i=0; i<n; i++)
			scanf("%d %d",&a[i].p,&a[i].m);
		sort(a,a+n,vs);
		int sum=0,ti=0;
		while(v) {
			if(v>=a[ti].m) {
				sum+=a[ti].m*a[ti].p;
				v-=a[ti].m;
			} else {
				sum+=v*a[ti].p;
				v=0;
			}
			ti++;
			if(ti==n)
				break;
		}
		printf("%d\n",sum);
	}
	return 0;
}

题目地址:【杭电】[2111]Saving HDU