题解 P2616 【[USACO10JAN]购买饲料II Buying Feed, II】

化学小哥 · 2016-09-14 22:24:30 · 题解

一个大贪心……

记录每个货物的价格为（m-t）*c，然后贪心……

#include<cstdio>
#include<algorithm>
using namespace std;
struct shu {int jia,num;}a[505];//jia 为价格   ，num为数量
int k,m,n,t,c,ans;
int compare(shu x,shu y)
{
    return x.jia<y.jia;
}
int main()
{
    scanf("%d%d%d",&k,&m,&n);
    for (int i=1;i<=n;i++)
    {scanf("%d%d%d",&t,&a[i].num,&c);a[i].jia=(m-t)+c;}//预处理
    sort(a+1,a+n+1,compare);//排序找最小
    for (int i=1;i<=n;i++)
    {ans+=min(k,a[i].num)*a[i].jia;
     k-=a[i].num;
     if (k<=0) break;//取最小值
    }
    printf("%d",ans);
}