P1208 [USACO1.3] 混合牛奶 Mixing Milk 洛谷

传送门：

知识点：贪心

思路：

1.很直接的贪心，只要当前cost值最小，最终满足需求的cost值一定最小

2.按照农夫单价排序（从低到高）；

代码如下：

#include <iostream>
#include <algorithm>

using namespace std;

struct node{
    int Max;
    int simple;
}f[ 5005 ];
int n, m;

int cmp ( node a, node b )
{
    return a.simple < b.simple;
}

int sum;

int main ( )
{
    scanf( "%d %d", &n, &m );
    for ( int i = 0 ; i < m; ++ i )
    {
        scanf( "%d %d", &f[ i ].simple, &f[ i ].Max );
    }
    sort ( f, f + m, cmp );
    for ( int i = 0; i < m && n > 0; ++ i )
    {
        // 取此农夫与剩余需求量的小值
        sum += (f[ i ].Max >= n ? n : f[ i ].Max) * f[ i ].simple;

        // 更新剩余量
        n -= f[ i ].Max;
    }
    printf ( "%d\n", sum );

    return 0;
}