Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# USACO Mixing Milk Problem

· ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```// 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

#include

#include

#include

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

``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.