DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Roger has posted 34 posts at DZone. View Full User Profile

USACO Mixing Milk Problem

12.19.2008
| 505 views |
  • submit to reddit
        // 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.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

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);

    x=0;
    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);
        x++;
    }

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