大意
给定n件东西的价值和单价,每件物品只能选择一次,求在总价值超过s的情况的最小代价
思路
我们肯定是每次选更便宜的最优啦,这就是一个简单的贪心
代码
/*
ID:hzbismy1
LANG:C++
TASK:milk
*/
#include<cstdio>
#include<algorithm>
using namespace std;pair<int,int>a[5001];//按单价排序
int n,s,ans;
signed main()
{
freopen("milk.in","r",stdin);
freopen("milk.out","w",stdout);
scanf("%d%d",&s,&n);
for(register int i=1,p,w;i<=n;i++) scanf("%d%d",&p,&w),a[i]=make_pair(p,w);
sort(a+1,a+1+n);//排序
for(register int i=1;i<=n&&s;s=max(0,s-a[i].second),i++)
ans+=min(s,a[i].second)*a[i].first;//计算
printf("%d\n",ans);//输出
}