📄 usaco 1_3_2 barn repair 题解_leokan的blog.mht
字号:
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 1.3.2 Barn Repair =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C201=C8=D5 =D0=C7=C6=DA=B6=FE =
13:32</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.3.2 Barn Repair</H2>
<DIV class=3Dt_msgfont>
<P>Barn Repair<BR>It was a dark and stormy night that ripped the =
roof and=20
gates off the stalls that hold Farmer John's cows. Happily, many =
of the=20
cows were on vacation, so the barn was not completely full. =
<BR><BR>The=20
cows spend the night in stalls that are arranged adjacent to each =
other in=20
a long line. Some stalls have cows in them; some do not. All =
stalls are=20
the same width. <BR><BR>Farmer John must quickly erect new boards =
in front=20
of the stalls, since the doors were lost. His new lumber supplier =
will=20
supply him boards of any length he wishes, but the supplier can =
only=20
deliver a small number of total boards. Farmer John wishes to =
minimize the=20
total length of the boards he must purchase. <BR><BR>Given M (1 =
<=3D M=20
<=3D 50), the maximum number of boards that can be purchased; S =
(1 <=3D=20
S <=3D 200), the total number of stalls; C (1 <=3D C <=3D =
S) the number=20
of cows in the stalls, and the C occupied stall numbers (1 <=3D =
stall_number <=3D S), calculate the minimum number of stalls =
that must be=20
blocked in order to block all the stalls that have cows in them.=20
<BR><BR>Print your answer as the total number of stalls blocked.=20
<BR><BR>PROGRAM NAME: barn1<BR>INPUT FORMAT<BR>Line 1: =
M, S,=20
and C (space separated) <BR>Lines 2-C+1: =
Each line=20
contains one integer, the number of an occupied=20
stall. <BR><BR>SAMPLE INPUT (file barn1.in) <BR>4 50=20
=
18<BR>3<BR>4<BR>6<BR>8<BR>14<BR>15<BR>16<BR>17<BR>21<BR>25<BR>26<BR>27<BR=
>30<BR>31<BR>40<BR>41<BR>42<BR>43<BR><BR>OUTPUT=20
FORMAT<BR>A single line with one integer that represents the total =
number=20
of stalls blocked. <BR>SAMPLE OUTPUT (file =
barn1.out)<BR>25<BR><BR>[One=20
minimum arrangement is one board covering stalls 3-8, one covering =
14-21,=20
one covering 25-31, and one covering 40-43.]<BR>Barn=20
Repair<BR>=D0=DE=C0=ED=C5=A3=C5=EF<BR><BR>=D2=EB by tim green =
<BR><BR> =20
=
=D4=DA=D2=BB=B8=F6=B1=A9=B7=E7=D3=EA=B5=C4=D2=B9=CD=ED,=C5=A9=C3=F1=D4=BC=
=BA=B2=B5=C4=C5=A3=C5=EF=B5=C4=CE=DD=B6=A5=A1=A2=C3=C5=B1=BB=B4=B5=B7=C9=C1=
=CB=A1=A3 =
=BA=C3=D4=DA=D0=ED=B6=E0=C5=A3=D5=FD=D4=DA=B6=C8=BC=D9=A3=AC=CB=F9=D2=D4=C5=
=A3=C5=EF=C3=BB=D3=D0=D7=A1=C2=FA=A1=A3=20
=
=CA=A3=CF=C2=B5=C4=C5=A3=D2=BB=B8=F6=BD=F4=B0=A4=D7=C5=C1=ED=D2=BB=B8=F6=B1=
=BB=C5=C5=B3=C9=D2=BB=D0=D0=C0=B4=B9=FD=D2=B9=A1=A3 =
=D3=D0=D0=A9=C5=A3=C5=EF=C0=EF=D3=D0=C5=A3=A3=AC=D3=D0=D0=A9=C3=BB=D3=D0=A1=
=A3 =
=CB=F9=D3=D0=B5=C4=C5=A3=C5=EF=D3=D0=CF=E0=CD=AC=B5=C4=BF=ED=B6=C8=A1=A3 =
=
=D7=D4=C3=C5=D2=C5=CA=A7=D2=D4=BA=F3,=C5=A9=C3=F1=D4=BC=BA=B2=BA=DC=BF=EC=
=D4=DA=C5=A3=C5=EF=D6=AE=C7=B0=CA=FA=C1=A2=C6=F0=D0=C2=B5=C4=C4=BE=B0=E5=A1=
=A3 =
=CB=FB=B5=C4=D0=C2=C4=BE=B2=C4=B9=A9=D3=A6=D5=DF=BD=AB=BB=E1=B9=A9=D3=A6=CB=
=FB=C8=CE=BA=CE=CB=FB=CF=EB=D2=AA=B5=C4=B3=A4=B6=C8,=B5=AB=CA=C7=B9=A9=D3=
=A6=D5=DF=D6=BB=C4=DC=CC=E1=B9=A9=D3=D0=CF=DE=CA=FD=C4=BF=B5=C4=C4=BE=B0=E5=
=A1=A3=20
=
=C5=A9=C3=F1=D4=BC=BA=B2=CF=EB=BD=AB=CB=FB=B9=BA=C2=F2=B5=C4=C4=BE=B0=E5=D7=
=DC=B3=A4=B6=C8=BC=F5=B5=BD=D7=EE=C9=D9=A1=A3 =B8=F8=B3=F6 M(1<=3D =
M<=3D50),=BF=C9=C4=DC=C2=F2=B5=BD=B5=C4=C4=BE=B0=E5=D7=EE=B4=F3=B5=C4=CA=
=FD=C4=BF;S(1<=3D=20
S<=3D200),=C5=A3=C5=EF=B5=C4=D7=DC=CA=FD;C(1 <=3D C =
<=3DS) =
=C5=A3=C5=EF=C0=EF=C5=A3=B5=C4=CA=FD=C4=BF,=BA=CD=C5=A3=CB=F9=D4=DA=B5=C4=
=C5=A3=C5=EF=B5=C4=B1=E0=BA=C5stall_number(1=20
<=3D stall_number <=3D =
S),=BC=C6=CB=E3=C0=B9=D7=A1=CB=F9=D3=D0=D3=D0=C5=A3=B5=C4=C5=A3=C5=EF=CB=F9=
=D0=E8=C4=BE=B0=E5=B5=C4=D7=EE=D0=A1=D7=DC=B3=A4=B6=C8=A1=A3 =
=CA=E4=B3=F6=CB=F9=D0=E8=C4=BE=B0=E5=B5=C4=D7=EE=D0=A1=D7=DC=B3=A4=B6=C8=D7=
=F7=CE=AA=B5=C4=B4=F0=B0=B8=A1=A3=20
<BR><BR>PROGRAM NAME: barn1 <BR><BR>INPUT FORMAT <BR><BR>=B5=DA 1 =
=D0=D0: M =A3=AC S =BA=CD=20
C(=D3=C3=BF=D5=B8=F1=B7=D6=BF=AA) <BR>=B5=DA 2 =B5=BD =
C+1=D0=D0: =20
=
=C3=BF=D0=D0=B0=FC=BA=AC=D2=BB=B8=F6=D5=FB=CA=FD=A3=AC=B1=ED=CA=BE=C5=A3=CB=
=F9=D5=BC=B5=C4=C5=A3=C5=EF=B5=C4=B1=E0=BA=C5=A1=A3 <BR><BR>SA=
MPLE INPUT (file barn1.in)=20
<BR><BR>4 50=20
=
18<BR>3<BR>4<BR>6<BR>8<BR>14<BR>15<BR>16<BR>17<BR>21<BR>25<BR>26<BR>27<BR=
>30<BR>31<BR>40<BR>41<BR>42<BR>43<BR>OUTPUT=20
FORMAT =
<BR><BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=B0=FC=BA=AC=D2=BB=B8=F6=D5=FB=CA=FD=
=B1=ED=CA=BE=CB=F9=D0=E8=C4=BE=B0=E5=B5=C4=D7=EE=D0=A1=D7=DC=B3=A4=B6=C8=A1=
=A3 <BR><BR>SAMPLE OUTPUT (file=20
barn1.out) <BR><BR>25 <BR><BR>[ =
=D2=BB=D6=D6=D7=EE=D3=C5=B5=C4=B0=B2=C5=C5=CA=C7=D3=C3=B0=E5=C0=B9=D7=A1=C5=
=A3=C5=EF3-8,14-21,25-31,40-43.]</P>
<P>=A1=A4</P>
<P>=A1=A4</P>
<P>=A1=A4</P>
<P></P>
<P><STRONG>=D3=C3=CC=B0=D0=C4=D7=F6=A3=A8TEXT Greedy =
Algorithm=C4=C7=C0=EF=D2=D1=BE=AD=B8=F8=C1=CB=C3=F7=CF=D4=B5=C4=CC=E1=CA=BE=
=A3=A9=A3=AC=C9=E8=C5=A3=C0=B8=CE=AA=A3=BA</STRONG></P>
<P><STRONG>123456789<BR>001100110</STRONG></P>
=
<P><STRONG>=D3=C31=BF=E9=C4=BE=B0=E5=B8=B2=B8=C73-8=A3=AC=BB=A8=C1=CB6=B5=
=C4=B3=A4=B6=C8=A3=AC=C8=BB=BA=F3=D4=D9=D4=DA=C0=EF=C3=E6=BC=F5=C8=A5=BF=D5=
=CF=B6=D7=EE=B4=F3=B5=C4=C5=A3=C0=B8n-1=B8=F6=A3=AC=B1=C8=C8=E75-6=B5=C40=
0=A3=AC=BC=F5=CD=EA=BA=F3=BE=CD=D3=D0n=BF=E9=C4=BE=B0=E5=A3=AC=C2=FA=D7=E3=
=CC=F5=BC=FE=A3=AC=D3=C9=D3=DA=CE=D2=C3=BF=B4=CE=B6=BC=CA=C7=BE=A1=C1=BF=BC=
=F5=C8=A5=B3=A4=B5=C4=C4=BE=B0=E5=A3=AC=CB=F9=D2=D4=CA=A3=D3=E0=B5=C4=CA=C7=
=D7=EE=D0=A1=B5=C4=A3=AC=CC=B0=D0=C4=D5=FD=C8=B7=D0=D4=B5=C3=B5=BD=D6=A4=C3=
=F7=A1=A3</STRONG></P>
=
<P><STRONG>=D5=E2=CC=E2=CE=D22=B4=CEac=A3=AC=B5=DA=D2=BB=B4=CE=BD=ABbarn1=
.out=B4=F2=B3=C9barn1,out=C1=CB=A3=AC=CC=AB=B2=BB=BB=AE=CB=E3!</STRONG></=
P>
<P><BR><STRONG>code=A3=BA</STRONG></P>
<P><STRONG>{<BR>TASK:barn1<BR>LANG:PASCAL<BR>}<BR>program=20
barn1;<BR>var<BR> =
n,s,c:integer;<BR> =20
a,b:array[1..200] of integer;<BR>procedure swap(var =
x,y:integer);<BR>var=20
t:integer;<BR>begin<BR> =
t:=3Dx;<BR> =20
x:=3Dy;<BR> y:=3Dt;<BR>end;</STRONG></P>
<P><STRONG>procedure =
qsa(f,l:integer);<BR>var<BR> =20
i,j,x:longint;<BR>begin<BR> =
i:=3Df;j:=3Dl;x:=3Da[(i+j) shr=20
1];<BR> =20
repeat<BR> while =
a[j]>x do=20
dec(j);<BR> while =
a[i]<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);dec(j);<BR> &=
nbsp; =20
end;<BR> until i>j;<BR> if =
i<l=20
then qsa(i,l);<BR> if j>f then=20
qsa(f,j);<BR>end;</STRONG></P>
<P><STRONG>procedure =
qsb(f,l:integer);<BR>var<BR> =20
i,j,x:longint;<BR>begin<BR> =
i:=3Df;j:=3Dl;x:=3Db[(i+j) shr=20
1];<BR> =20
repeat<BR> while =
b[j]>x do=20
dec(j);<BR> while =
b[i]<x do=20
inc(i);<BR> if i<=3Dj =
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p;=20
=
swap(b[i],b[j]);<BR>  =
; =20
=
inc(i);dec(j);<BR> &=
nbsp; =20
end;<BR> until i>j;<BR> if =
i<l=20
then qsb(i,l);<BR> if j>f then=20
qsb(f,j);<BR>end;</STRONG></P>
<P><BR><STRONG>procedure =
init;{=B3=F5=CA=BC=BB=AF}<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'barn1.in');reset(input);<BR> =20
readln(n,s,c);<BR> for i:=3D1 to c=20
do<BR> =20
readln(a[i]);<BR> =
qsa(1,c);<BR> =20
close(input);<BR>end;</STRONG></P>
<P><STRONG>procedure work;<BR>var<BR> =20
i,s:integer;<BR>begin<BR> =20
assign(output,'barn1.out');rewrite(output);<BR> =20
s:=3Da[c]-a[1]+1;<BR> for i:=3D2 to c=20
do<BR> =20
b[i-1]:=3Da[i]-a[i-1]-1;<BR> =20
qsb(1,c-1);{=B6=D4=BC=E4=CF=B6=C5=C5=D0=F2}<BR> =
for i:=3D1 to n-1=20
do<BR> =20
=
dec(s,b[c-i]);{=B3=FD=C8=A5n-1=B8=F6=D7=EE=B4=F3=B5=C4=BC=E4=CF=B6}<BR>&n=
bsp; =20
writeln(s);<BR> =20
=
close(output);<BR>end;<BR>begin<BR>init;<BR>work;<BR>end.</STRONG></P>
<P></P>
<P></P>
=
<P><STRONG>=BB=B9=CA=C7=BF=B4=CF=C2USACO=B5=C4=B7=D6=CE=F6=A3=AC=D5=FB=CC=
=E5=CB=BC=CF=EB=D2=BB=D1=F9=A3=AC=B5=DA=B6=FE=D6=D6=BE=DF=CC=E5=B9=FD=B3=CC=
=B6=BC=BA=CD=CE=D2=D2=BB=D1=F9=A1=A3</STRONG></P>
<P><STRONG>=A1=A4</STRONG></P>
<P><STRONG>=A1=A4</STRONG></P>
<P><STRONG>=A1=A4</STRONG></P>
<P><STRONG>=A1=A4</STRONG></P>
<P><STRONG>If we can purchase M boards, then we can leave =
unblocked M-1=20
runs of stalls without cows in them, in addition to any stalls on =
the=20
leftmost side that don't have cows and any stalls on the rightmost =
side=20
that don't have cows. </STRONG></P>
<P><STRONG>We input the list of cows in stalls, storing into an =
array=20
whether or not there is a cow in a particular stall. Then we walk =
the=20
array counting sizes of runs of cowless stalls. We sort the list =
of sizes=20
and pick the M-1 largest ones as the stalls that will remain =
uncovered.=20
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXSTALL 200
int hascow[MAXSTALL];
int
intcmp(const void *va, const void *vb)
{
return *(int*)vb - *(int*)va;
}
void
main(void)
{
FILE *fin, *fout;
int n, m, nstall, ncow, i, j, c, lo, hi, nrun;
int run[MAXSTALL];
fin =3D fopen("barn1.in", "r");
fout =3D fopen("barn1.out", "w");
=20
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d %d %d", &m, &nstall, &ncow);
for(i=3D0; i<ncow; i++) {
fscanf(fin, "%d", &c);
hascow[c-1] =3D 1;
}
n =3D 0; /* answer: no. of uncovered stalls */
/* count empty stalls on left */
for(i=3D0; i<nstall && !hascow[i]; i++)
n++;
lo =3D i;
/* count empty stalls on right */
for(i=3Dnstall-1; i>=3D0 && !hascow[i]; i--)
n++;
hi =3D i+1;
/* count runs of empty stalls */
nrun =3D 0;
i =3D lo;
while(i < hi) {
while(hascow[i] && i<hi)
i++;
for(j=3Di; j<hi && !hascow[j]; j++)
;
run[nrun++] =3D j-i;
i =3D j;
}
/* sort list of runs */
qsort(run, nrun, sizeof(run[0]), intcmp);
/* uncover best m-1 runs */
for(i=3D0; i<nrun && i<m-1; i++)
n +=3D run[i];
fprintf(fout, "%d\n", nstall-n);
exit(0);
}
</STRONG></PRE>
<P><STRONG><EM>Alexandru Tudorica's solution might be =
simpler:</EM>=20
</STRONG></P><PRE><STRONG>var f:text;
a,b:array[1..1000] of longint;
i,m,s,c,k:longint;
procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
i:=3Dl; j:=3Dr; x:=3Da[(l+r) div 2];
repeat
while a[i]<x do i:=3Di+1;
while x<a[j] do j:=3Dj-1;
if i<=3Dj then begin
y:=3Da[i]; a[i]:=3Da[j]; a[j]:=3Dy;
i:=3Di+1;
j:=3Dj-1;
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure qsortb(l,r:longint);
var i,j,x,y:longint;
begin
i:=3Dl; j:=3Dr; x:=3Db[(l+r) div 2];
repeat
while b[i]<x do i:=3Di+1;
while x<b[j] do j:=3Dj-1;
if i<=3Dj then
begin
y:=3Db[i]; b[i]:=3Db[j]; b[j]:=3Dy;
i:=3Di+1;
j:=3Dj-1;
end;
until i>j;
if l<j then qsortb(l,j);
if i<r then qsortb(i,r);
end;
begin
assign(f,'barn1.in');
reset(f);
readln(f,m,k,c);
for i:=3D1 to c do readln(f,a[i]);
qsort(1,c);
for i:=3D1 to c-1 do b[i]:=3Da[i+1]-a[i]-1;
qsortb(1,c-1);
for i:=3Dc-1 downto (c-m+1) do s:=3Ds+b[i];
close(f);
assign(f,'barn1.out');
rewrite(f);
writeln(f,a[c]-a[1]-s+1);
close(f);
end.</STRONG></PRE></DIV></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/069c4fa7679dd791d043580e.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 1.3.1 Mixing Milk =CC=E2=BD=E2', 'USACO 1.3.1 =
Mixing Milk =
=CC=E2=BD=E2','/leokan/blog/item/334b3787da7c2a2ec65cc38c.html'];
var post =3D =
[true,'=B7=A2=B8=F6=CA=D3=C6=C1=A3=A8=D1=DB=BE=A6=B4=ED=BE=F5=B5=C4=BD=E2=
=C3=DC=A3=A9','=B7=A2=B8=F6=CA=D3=C6=C1=A3=A8=D1=DB=BE=A6=B4=ED=BE=F5=B5=C4=
=BD=E2=C3=DC=A3=A9', '/leokan/blog/item/058b8a44cb4e0548500ffe16.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -