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

幽界の冥神 · 2017-10-09 21:52:37 · 题解

#include "cstdio"
#include "algorithm"
using namespace std;
struct food{int val,num;}f[102];//num为这个商店的存货,val为在这个商店买一份食物的价钱
int number,s,n,ans=0;
bool cmp(food a,food b){return a.val<b.val;}//从小到大排序 
int Min(int a,int b){return a<b?a:b;}
int main(){
    scanf("%d%d%d",&number,&s,&n);//number为总共要买的食物,s为总路程,n为商店数 
    for(int i=1,a,b;i<=n;i++){
        scanf("%d%d%d",&a,&f[i].num ,&b);
        f[i].val=s-a+b;//在这个商店买一份食物的价钱 
    }
    sort(f+1,f+1+n,cmp);//排序,取最小值 
    for(int i=1;i<=n&&number>0;i++){
        ans+=Min(number,f[i].num)*f[i].val;//每到一个商店就取光光 
        number-=f[i].num;//剩下需要买的食物 
    }
    printf("%d",ans);//输出 
    return 0;
}

个人认为这是比较简短的代码了，缩进不大好看，见谅。。。 一般贪心必将配合排序（至少我做的题目是这样的）不排序的贪心很可能有问题。。。

基本就是这样了，注释应该还蛮详细的