Over a million developers have joined DZone.

USACO Mixing Milk Problem

DZone's Guide to

USACO Mixing Milk Problem

Free Resource
// USACO's Mixing Milk Problem -- a very straightforward Greedy Algorithm. It could be optimized to "bucket
// sort" on price, but this way was quick to code (and gave me experience with C's qsort function.


typedef struct PriceAmt PriceAmt;

struct PriceAmt {
    int price;
    int amt;

int compare (const void * va, const void * vb) {
    PriceAmt *a, *b;
    a = (PriceAmt*)va;
    b = (PriceAmt*)vb;

    if (a->price > b->price) return 1;
    if (a->price < b->price) return -1;
    return 0;

int main(void) {
    FILE *fin, *fout;
    int dayAmt;
    int nFarmers;
    int curAmt = 0;
    int curPrice = 0;

    fin = fopen("milk.in", "r");
    fout = fopen("milk.out", "w");
    fscanf(fin, "%d %d", &dayAmt, &nFarmers);

    PriceAmt amounts[nFarmers];
    memset(amounts, 0, sizeof(PriceAmt));
    int x;
    for (x=0; x < nFarmers; x++){
        fscanf(fin, "%d %d", &amounts[x].price, &amounts[x].amt);
    qsort(amounts, nFarmers, sizeof(PriceAmt), compare);

    int curTake = 0;
    while (curAmt < dayAmt) {
        if ((curAmt + amounts[x].amt) < dayAmt) {
            curTake = amounts[x].amt;
        } else {
            /* take only what you need */
            curTake = dayAmt - curAmt;
        curAmt += curTake;
        curPrice += (curTake * amounts[x].price);

    fprintf(fout, "%d\n", curPrice);


Opinions expressed by DZone contributors are their own.


Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.


{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}