题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2111
好久不刷题,拿到水题切了切,,,,,题意刚开始都没有理解,,,,真是弱了,,,,
简单贪心,,,,注意分割后的价值和对应的体积成正比
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <ctype.h>
#include <iomanip>
#include <queue>
#include <stdlib.h>
using namespace std; struct node{
int val,vol;
}s[];
bool cmp(node x,node y)
{
return x.val>y.val;
}
int main()
{
int m,n,i;
while(scanf("%d",&m),m)
{
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%d%d",&s[i].val,&s[i].vol);
sort(s,s+n,cmp);
int sum=;
for(i=;i<n;i++)
{
if(m>s[i].vol)
{
sum+=s[i].val*s[i].vol;
m-=s[i].vol;
}
else
{
sum+=m*s[i].val;
break;
}
}
printf("%d\n",sum);
}
return ;
}