📄 usaco 1_3_1 mixing milk 题解_leokan的blog.mht
字号:
<DIV class=3Ddate>2008=C4=EA01=D4=C201=C8=D5 =D0=C7=C6=DA=B6=FE =
10:08</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<DIV align=3Dleft>
<H2>USACO 1.3.1 Mixing Milk</H2></DIV>
<DIV>
<P>Mixing Milk<BR>Since milk packaging is such a low margin =
business, it=20
is important to keep the price of the raw product (milk) as low as =
possible. Help Merry Milk Makers get the milk they need in the =
cheapest=20
possible manner. <BR><BR>The Merry Milk Makers company has several =
farmers=20
from which they may buy milk, and each one has a (potentially) =
different=20
price at which they sell to the milk packing plant. Moreover, as a =
cow can=20
only produce so much milk a day, the farmers only have so much =
milk to=20
sell per day. Each day, Merry Milk Makers can purchase an integral =
amount=20
of milk from each farmer, less than or equal to the farmer's =
limit.=20
<BR><BR>Given the Merry Milk Makers' daily requirement of milk, =
along with=20
the cost per gallon and amount of available milk for each farmer,=20
calculate the minimum amount of money that it takes to fulfill the =
Merry=20
Milk Makers' requirements. <BR><BR>Note: The total milk produced =
per day=20
by the farmers will be sufficient to meet the demands of the Merry =
Milk=20
Makers. <BR><BR>PROGRAM NAME: milk<BR>INPUT FORMAT<BR>Line =
1: =20
Two integers, N and M. <BR>The first value, N, (0 <=3D N =
<=3D 2,000,000)=20
is the amount of milk that Merry Milk Makers' want per day. The =
second, M,=20
(0 <=3D M <=3D 5,000) is the number of farmers that they may =
buy from.=20
<BR><BR>Lines 2 through M+1: The next M lines each =
contain two=20
integers, Pi and Ai. <BR>Pi (0 <=3D Pi <=3D 1,000) is price =
in cents=20
that farmer i charges.<BR>Ai (0 <=3D Ai <=3D 2,000,000) is =
the amount of=20
milk that farmer i can sell to Merry Milk Makers per=20
day. <BR><BR><BR>SAMPLE INPUT (file milk.in) <BR>100 =
5<BR>5=20
20<BR>9 40<BR>3 10<BR>8 80<BR>6 30<BR><BR>OUTPUT FORMAT<BR>A =
single line=20
with a single integer that is the minimum price that Merry Milk =
Makers can=20
get their milk at for one day. <BR><BR>SAMPLE OUTPUT (file=20
milk.out)<BR>630<BR><BR><BR><BR>Mixing =
Milk<BR><BR>=BB=EC=BA=CF=C5=A3=C4=CC<BR><BR>=D2=EB by tim=20
=
green<BR><BR><BR>=C5=A3=C4=CC=B0=FC=D7=B0=CA=C7=D2=BB=B8=F6=C8=E7=B4=CB=B5=
=CD=C0=FB=C8=F3=B5=C4=C9=FA=D2=E2,=CB=F9=D2=D4=BE=A1=BF=C9=C4=DC=B5=CD=B5=
=C4=BF=D8=D6=C6=B3=F5=BC=B6=B2=FA=C6=B7(=C5=A3=C4=CC)=B5=C4=BC=DB=B8=F1=B1=
=E4=B5=C4=CA=AE=B7=D6=D6=D8=D2=AA=A1=A3<BR>=C7=EB=B0=EF=D6=FA=BF=EC=C0=D6=
=B5=C4=C5=A3=C4=CC=D6=C6=D4=EC=D5=DF(Merry=20
Milk=20
=
Makers)=D2=D4=BF=C9=C4=DC=B5=C4=D7=EE=C1=AE=BC=DB=B5=C4=B7=BD=CA=BD=C8=A1=
=B5=C3=CB=FB=C3=C7=CB=F9=D0=E8=B5=C4=C5=A3=C4=CC=A1=A3<BR>=BF=EC=C0=D6=B5=
=C4=C5=A3=C4=CC=D6=C6=D4=EC=B9=AB=CB=BE=B4=D3=D2=BB=D0=A9=C5=A9=C3=F1=C4=C7=
=B9=BA=C2=F2=C5=A3=C4=CC=A3=AC=C3=BF=B8=F6=C5=A9=C3=F1=C2=F4=B8=F8=C5=A3=C4=
=CC=D6=C6=D4=EC=B9=AB=CB=BE=B5=C4=BC=DB=B8=F1=B2=BB=D2=BB=B6=A8=CF=E0=CD=AC=
=A1=A3<BR>=B6=F8=C7=D2,=C8=E7=D2=BB=D6=BB=C4=B8=C5=A3=D2=BB=CC=EC=D6=BB=C4=
=DC=C9=FA=B2=FA=D2=BB=B6=A8=C1=BF=B5=C4=C5=A3=C4=CC,=C5=A9=C3=F1=C3=BF=D2=
=BB=CC=EC=D6=BB=D3=D0=D2=BB=B6=A8=C1=BF=B5=C4=C5=A3=C4=CC=BF=C9=D2=D4=C2=F4=
=A1=A3<BR>=C3=BF=CC=EC,=BF=EC=C0=D6=B5=C4=C5=A3=C4=CC=D6=C6=D4=EC=D5=DF=B4=
=D3=C3=BF=B8=F6=C5=A9=C3=F1=C4=C7=B9=BA=C2=F2=D2=BB=B6=A8=C1=BF=B5=C4=C5=A3=
=C4=CC,=C9=D9=D3=DA=BB=F2=B5=C8=D3=DA=C5=A9=C3=F1=CB=F9=C4=DC=CC=E1=B9=A9=
=B5=C4=D7=EE=B4=F3=D6=B5=A1=A3<BR>=B8=F8=B3=F6=BF=EC=C0=D6=C5=A3=C4=CC=D6=
=C6=D4=EC=D5=DF=B5=C4=C3=BF=C8=D5=B5=C4=C5=A3=C4=CC=D0=E8=C7=F3,=C1=AC=CD=
=AC=C3=BF=B8=F6=C5=A9=C3=F1=B5=C4=BF=C9=CC=E1=B9=A9=B5=C4=C5=A3=C4=CC=C1=BF=
=BA=CD=C3=BF=BC=D3=C2=D8=B5=C4=BC=DB=B8=F1,=C7=EB=BC=C6=CB=E3=BF=EC=C0=D6=
=B5=C4=C5=A3=C4=CC=D6=C6=D4=EC=D5=DF=CB=F9=D2=AA=B8=B6=B3=F6=C7=AE=B5=C4=D7=
=EE=D0=A1=D6=B5=A1=A3<BR>=D7=A2=D2=E2:<BR>=C3=BF=CC=EC=C5=A9=C3=F1=C9=FA=B2=
=FA=B5=C4=C5=A3=C4=CC=B5=C4=D7=DC=CA=FD=B6=D4=BF=EC=C0=D6=B5=C4=C5=A3=C4=CC=
=D6=C6=D4=EC=D5=DF=C0=B4=CB=B5=D7=E3=B9=BB=B5=C4=A1=A3<BR><BR><BR>PROGRAM=
=20
NAME: milk<BR><BR>INPUT FORMAT<BR>=B5=DA 1 =
=D0=D0:=B6=FE=B8=F6=D5=FB=CA=FD, N =BA=CD =
M=A1=A3<BR>=B5=DA=D2=BB=B8=F6=CA=FD=D6=B5,N,(0<=3D=20
=
N<=3D2,000,000)=CA=C7=BF=EC=C0=D6=B5=C4=C5=A3=C4=CC=D6=C6=D4=EC=D5=DF=B5=
=C4=D2=BB=CC=EC=D0=E8=D2=AA=C5=A3=C4=CC=B5=C4=CA=FD=C1=BF=A1=A3<BR>=B5=DA=
=B6=FE=B8=F6=CA=FD=D6=B5,M,(0<=3D=20
=
M<=3D5,000)=CA=C7=CB=FB=C3=C7=BF=C9=C4=DC=B4=D3=C5=A9=C3=F1=C4=C7=C2=F2=
=B5=BD=B5=C4=CA=FD=C4=BF=A1=A3<BR>=B5=DA 2 =B5=BD M+1 =
=D0=D0:=C3=BF=D0=D0=B6=FE=B8=F6=D5=FB=CA=FD,Pi =BA=CD =
Ai=A1=A3<BR>Pi(0<=3D=20
Pi<=3D1,000) =CA=C7=C5=A9=C3=F1 i =
=C5=A3=C4=CC=B5=C4=BC=DB=B8=F1=A1=A3<BR>Ai(0 <=3D Ai <=3D =
2,000,000)=CA=C7=C5=A9=C3=F1 i=20
=
=D2=BB=CC=EC=C4=DC=C2=F4=B8=F8=BF=EC=C0=D6=B5=C4=C5=A3=C4=CC=D6=C6=D4=EC=D5=
=DF=B5=C4=C5=A3=C4=CC=CA=FD=C1=BF=A1=A3<BR><BR>SAMPLE INPUT (file =
milk.in) <BR>100 5<BR>5=20
20<BR>9 40<BR>3 10<BR>8 80<BR>6 30<BR><BR>OUTPUT=20
=
FORMAT<BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=B0=FC=BA=AC=B5=A5=B6=C0=B5=C4=D2=
=BB=B8=F6=D5=FB=CA=FD=A3=AC=B1=ED=CA=BE=BF=EC=C0=D6=B5=C4=C5=A3=C4=CC=D6=C6=
=D4=EC=D5=DF=C4=C3=B5=BD=CB=F9=D0=E8=B5=C4=C5=A3=C4=CC=CB=F9=D2=AA=B5=C4=D7=
=EE=D0=A1=B7=D1=D3=C3<BR><BR>SAMPLE OUTPUT=20
(file milk.out)<BR>630</P>
<P><STRONG>`</STRONG></P>
<P><STRONG>`</STRONG></P>
<P><STRONG>`</STRONG></P>
<P><STRONG>`</STRONG></P>
=
<P><STRONG>=C5=C5=D0=F2=A3=AC=C8=BB=BA=F3=D3=C3=CC=B0=D0=C4=D7=F6=A3=AC=C3=
=BF=B4=CE=C8=A1=D7=EE=B1=E3=D2=CB=B5=C4=C2=F2=A1=A3</STRONG></P></DIV>
<P =
align=3Dleft><STRONG>{<BR>TASK:milk<BR>LANG:PASCAL<BR>}<BR>program=20
milk;<BR>type<BR> =20
xy=3Drecord<BR> =20
x:integer;<BR> =20
y:longint;<BR> end;<BR> =20
arr=3Darray[0..5000] of=20
xy;<BR>var<BR>a:arr;<BR>n,m,money:longint;<BR>procedure swap(var=20
x,y:xy);<BR>var<BR> =
t:xy;<BR>begin<BR> =20
t:=3Dx;<BR> x:=3Dy;<BR> =20
y:=3Dt;<BR>end;</STRONG></P>
<P align=3Dleft><STRONG>procedure=20
qs(f,l:integer);<BR>var<BR> =20
i,j:longint;<BR> =
x:xy;<BR>begin<BR> =20
i:=3Df;j:=3Dl;<BR> x:=3Da[(i+j)shr =
1];<BR> =20
repeat<BR> =20
while(a[j].x>x.x)do=20
dec(j);<BR> =20
while(a[i].x<x.x)do=20
inc(i);<BR> if i<=3Dj =
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p;=20
=
swap(a[i],a[j]);<BR>  =
; =20
=
inc(i);<BR> &n=
bsp;=20
=
dec(j);<BR> &n=
bsp;=20
end;<BR> until i>j;<BR> if =
i<l=20
then qs(i,l);<BR> if i>f then=20
qs(f,j);<BR>end;</STRONG></P>
<P align=3Dleft><BR><STRONG>procedure =
init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'milk.in');reset(input);<BR> =20
readln(n,m);<BR> for i:=3D1 to m=20
do<BR> =20
readln(a[i].x,a[i].y);<BR> =20
close(input);<BR> qs(1,m);<BR>end;<BR>procedure=20
main;<BR>var<BR> =
p:integer;<BR> =20
now:longint;<BR>begin<BR> =20
now:=3D0;p:=3D1;money:=3D0;<BR> while now<n=20
do<BR> =20
begin<BR> if =
now+a[p].y>n=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p;=20
=
inc(money,(n-now)*a[p].x);<BR> &=
nbsp; =20
=
now:=3Dn;<BR> =
=20
=
end<BR> =
=20
else=20
=
begin<BR> &nbs=
p;=20
=
inc(money,a[p].x*a[p].y);<BR> &n=
bsp; =20
=
inc(now,a[p].y);<BR>  =
; =20
end;<BR> =20
inc(p);<BR> =20
end;<BR>end;<BR>procedure out;<BR>begin<BR> =20
writeln(money);<BR>end;<BR>begin<BR> =20
init;<BR> =20
assign(output,'milk.out');rewrite(output);<BR> =
if=20
n<>0 then begin main;out;end else=20
writeln(0);<BR>close(output);<BR>end.</STRONG></P>
<P align=3Dleft><STRONG>`</STRONG></P>
<P align=3Dleft><STRONG>`</STRONG></P>
<P align=3Dleft><STRONG>`</STRONG></P>
<P align=3Dleft><STRONG>`</STRONG></P>
<P align=3Dleft><STRONG>`</STRONG></P>
<P align=3Dleft></P>
<P align=3Dleft></P>
<P align=3Dleft></P>
<P align=3Dleft></P>
<P =
align=3Dleft><STRONG>usaco=B5=C4=B7=D6=CE=F6=BA=DC=C7=BF=B4=F3=A3=A1=A3=A1=
=A3=A8=BF=B4=D7=EE=BA=F3=D2=BB=D6=D6=A3=ACO(n)!!!=A3=A9</STRONG></P>
<P align=3Dleft></P>
<P align=3Dleft></P>
<P align=3Dleft></P>
<P align=3Dleft></P>
<P align=3Dleft></P><STRONG>
<P align=3Dleft>Since we're acquiring things that are all of the =
same size=20
(in this case, units of milk), a greedy solution will suffice: we =
sort the=20
farmers by price, and then buy milk from the farmers with the =
lowest=20
prices, always completely exhausting one farmer's supply before =
moving on=20
to the next one.</P>
<P align=3Dleft>To do this, we read the input into Farmer =
structures, sort=20
the array by price, and then walk the array, buying milk until =
we've got=20
all the milk we want.</P>
<DIV align=3Dleft><PRE>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXFARMER 5000
typedef struct Farmer Farmer;
struct Farmer {
int p; /* price per gallon */
int a; /* amount to sell */
};
int
farmcmp(const void *va, const void *vb)
{
return ((Farmer*)va)->p - ((Farmer*)vb)->p;
}
int nfarmer;
Farmer farmer[MAXFARMER];
void
main(void)
{
FILE *fin, *fout;
int i, n, a, p;
fin =3D fopen("milk.in", "r");
fout =3D fopen("milk.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d %d", &n, &nfarmer);
for(i=3D0; i<nfarmer; i++)
fscanf(fin, "%d %d", &farmer[i].p, &farmer[i].a);
qsort(farmer, nfarmer, sizeof(farmer[0]), farmcmp);
p =3D 0;
for(i=3D0; i<nfarmer && n > 0; i++) {
/* take as much as possible from farmer[i], up to amount n */
a =3D farmer[i].a;
if(a > n)
a =3D n;
p +=3D a*farmer[i].p;
n -=3D a;
}
fprintf(fout, "%d\n", p);
exit(0);
}</PRE></DIV>
<P align=3Dleft><BR><BOLD></BOLD>Ran Pang of Canada writes:</P>
<P align=3Dleft>Here is a program that solves the problem in =
linear time=20
(with respect to the maximum price, and number of farmers, since =
we have=20
to read in the data anyway), while I think the qsort used by the =
solution=20
would consume O(n log n), where n is the number of farmers.</P>
<DIV align=3Dleft><PRE>#include<stdio.h>
#define MAXPRICE 1001
int amount_for_price[MAXPRICE]=3D{0};
int N, M;
int Cal(void);
int Read(void);
int main(void) {
Read();
Cal();
return 0;
}
int Cal(void) {
int i;
int price_total=3D0;
int milk_total=3D0;
for(i=3D0;i<MAXPRICE;i++) {
if(amount_for_price[i]) {
if(milk_total+amount_for_price[i]<N) {
price_total+=3D(i*amount_for_price[i]);
milk_total+=3Damount_for_price[i];
}
else {
int amount_needed =3D N-milk_total;
price_total+=3D(i*amount_needed);
break;
}
}
}
{
FILE* out=3Dfopen("milk.out","w");
fprintf(out,"%d\n",price_total);
fclose(out);
}
return 0;
}
int Read(void) {
FILE* in =3D fopen("milk.in","r");
int i, price, amount;
fscanf(in,"%d %d",&N,&M);
for(i=3D0;i<M;i++) {
fscanf(in, "%d %d", &(price), &(amount));
amount_for_price[price]+=3Damount;
}
fclose(in);
return 0;
}</PRE></DIV>
<P align=3Dleft>\f2Here is another solution from SVK's Adam =
Okruhlica\fP</P>
<P align=3Dleft>It is unnecessary to sort the prices with =
quicksort in=20
O(n.lg.n) time, because there is an upper limit of the a single =
price=20
($1000) and we know that all prices are integral. We can sort this =
array=20
with count sort. We establish a 'box' for each of the available =
prices=20
(0..1000). We save the input to an array. Then we iterate through =
each=20
farmer and we memoize his index in the (0..1000) array on index =
equivalent=20
to the price he offers us. Hence there can be more farmers =
offering the=20
same price we put them in a linked list. Finally we iterate the =
array from=20
0 to 1000 andpick the farmers' indexes from the linked lists. It's =
pretty=20
easy to implement, and the time complexity is O(n).</P>
<DIV align=3Dleft><PRE>program milk;
type pList =3D ^List;
List =3D record
farmer:longint;
next:pList;
end;
HeadList =3D record
head:pList;
tail:pList;
end;
var fIn,fOut:text;
sofar,i,x,want,cnt,a,b:longint;
sorted,cost,amount:array[1..5010] of longint;
csort:array[0..1010] of HeadList;
t:pList;
begin
assign(fIn,'milk.in');reset(fIn);
assign(fOut,'milk.out'); rewrite(fOut);
readln(fIn,want,cnt);
for i:=3D1 to cnt do readln(fIn,cost[i],amount[i]);
for i:=3D0 to 1000 do begin
new(csort[i].head);
csort[i].tail:=3Dcsort[i].head;
csort[i].head^.farmer:=3D-1;
end;
{Cast indexes into the array}
for i:=3D1 to cnt do begin
t:=3Dcsort[cost[i]].tail;
if t^.farmer =3D -1 then t^.farmer:=3Di;
new(t^.next);
t^.next^.farmer:=3D-1;
csort[cost[i]].tail:=3Dt^.next;
end;
{Pick indexes}
x:=3D1;
for i:=3D0 to 1000 do begin
t:=3Dcsort[i].head;
while t^.farmer > 0 do begin
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -