[USACO] 1.3 Mixing Milk(Greedy Algorithm)

Greedy 알고리즘의 가장 간단한 예이다. 가장 싼 우유부터 원하는 양까지 사들이면 된다.

int main() {

    ofstream fout ("milk.out");
    ifstream fin ("milk.in");

    int n, m;
    fin >> n >> m;
    vector< pair<int, int> > d;
    REP(i, m)
    {
        int a, b;
        fin >> a >> b;
        d.pb(make_pair(a, b));
    }
    sort(ALL(d));

    int cur = 0, ret = 0;
    REP(i, m)
    {
        if(n-cur > d[i].second )
        {
            cur += d[i].second;
            ret += d[i].first*d[i].second;
        }
        else
        {
            ret += (n-cur)*d[i].first;
            break;
        }
    }

    fout << ret << endl;
    return 0;
}