📄 usaco 2_1_3 sorting a three-valued sequence 题解_leokan的blog.mht
字号:
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</A> =
</DIV></DIV>
<DIV class=3Dstage>
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<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>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.1.3 Sorting a Three-Valued Sequence =
=CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C227=C8=D5 =D0=C7=C6=DA=C8=D5 =
23:48</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<P></P>
<P><FONT size=3D5><STRONG>USACO 2.1.3 Sorting a Three-Valued=20
Sequence</STRONG></FONT></P>
<DIV class=3Dt_msgfont>Sorting a Three-Valued Sequence <BR>IOI'96 =
- Day 2=20
<BR>Sorting is one of the most frequently performed computational =
tasks.=20
Consider the special sorting problem in which the records to be =
sorted=20
have at most three different key values. This happens for instance =
when we=20
sort meda<SPAN class=3Dt_tag =
href=3D"tag.php?name=3Dlis">lis</SPAN>ts of a=20
competition according to medal value, that is, gold meda<SPAN =
class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>ts come first, followed by =
silver, and=20
bronze meda<SPAN class=3Dt_tag =
href=3D"tag.php?name=3Dlis">lis</SPAN>ts come=20
last. <BR><BR>In this task the possible key values are the =
integers 1, 2=20
and 3. The required sorting order is non-decreasing. However, =
sorting has=20
to be accomplished by a sequence of exchange operations. An =
exchange=20
operation, defined by two position numbers p and q, exchanges the =
elements=20
in positions p and q. <BR><BR>You are given a sequence of key =
values.=20
Write a program that computes the minimal number of exchange =
operations=20
that are necessary to make the sequence sorted. <BR><BR>PROGRAM =
NAME:=20
sort3<BR>INPUT FORMAT<BR>Line 1: N (1 <=3D N =
<=3D 1000), the=20
number of records to be sorted <BR>Lines 2-N+1: A =
single=20
integer from the set {1, 2, 3} <BR><BR>SAMPLE INPUT (file =
sort3.in)=20
<BR>9<BR>2<BR>2<BR>1<BR>3<BR>3<BR>3<BR>2<BR>3<BR>1<BR><BR>OUTPUT=20
FORMAT<BR>A single line containing the number of exchanges =
required=20
<BR>SAMPLE OUTPUT (file sort3.out)<BR>4<BR><BR><BR><BR>Sorting a=20
Three-Valued Sequence <BR><BR>=C8=FD=D6=B5=B5=C4<SPAN =
class=3Dt_tag=20
href=3D"tag.php?name=3D%C5%C5%D0%F2">=C5=C5=D0=F2</SPAN><BR>IOI'96 =
- Day 2 <BR><BR>=D2=EB by=20
=
!Starliu<BR><BR>=C5=C5=D0=F2=CA=C7=D2=BB=D6=D6=BA=DC=C6=B5=B7=B1=B5=C4=BC=
=C6=CB=E3=C8=CE=CE=F1=A1=A3=CF=D6=D4=DA=BF=BC=C2=C7=D7=EE=B6=E0=D6=BB=D3=D0=
=C8=FD=D6=B5=B5=C4=C5=C5=D0=F2=CE=CA=CC=E2=A1=A3=D2=BB=B8=F6=CA=B5=BC=CA=B5=
=C4=C0=FD=D7=D3=CA=C7=A3=AC=B5=B1=CE=D2=C3=C7=B8=F8=C4=B3=CF=EE=BE=BA=C8=FC=
=B5=C4=D3=C5=CA=A4=D5=DF=B0=B4=BD=F0=D2=F8=CD=AD=C5=C6=D0=F2=B5=C4=CA=B1=BA=
=F2=A1=A3<BR><BR>=D4=DA=D5=E2=B8=F6=C8=CE=CE=F1=D6=D0=BF=C9=C4=DC=B5=C4=D6=
=B5=D6=BB=D3=D0=C8=FD=D6=D61=A3=AC2=BA=CD3=A1=A3=CE=D2=C3=C7=D3=C3=BD=BB=BB=
=BB=B5=C4=B7=BD=B7=A8=B0=D1=CB=FB=C5=C5=B3=C9=C9=FD=D0=F2=B5=C4=A1=A3<BR>=
<BR>=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=BC=C6=CB=E3=B3=F6=A3=AC=B8=F8=B6=A8=B5=
=C4=D2=BB=B8=F61,2,3=D7=E9=B3=C9=B5=C4=CA=FD=D7=D6=D0=F2=C1=D0=A3=AC=C5=C5=
=B3=C9=C9=FD=D0=F2=CB=F9=D0=E8=B5=C4=D7=EE=C9=D9=BD=BB=BB=BB=B4=CE=CA=FD=A1=
=A3<BR><BR>PROGRAM=20
NAME: sort3<BR>INPUT FORMAT<BR>Line 1: <BR>N (1 <=3D N <=3D=20
1000)<BR><BR>Lines 2-N+1: =
<BR>=C3=BF=D0=D0=D2=BB=B8=F6=CA=FD=D7=D6=A3=AC=B9=B2N=D0=D0=A1=A3=A3=A81.=
.3=A3=A9<BR><BR><BR>SAMPLE INPUT=20
(file sort3.in)=20
<BR>9<BR>2<BR>2<BR>1<BR>3<BR>3<BR>3<BR>2<BR>3<BR>1<BR>OUTPUT=20
=
FORMAT<BR>=B9=B2=D2=BB=D0=D0=A3=AC=D2=BB=B8=F6=CA=FD=D7=D6=A1=A3=B1=ED=CA=
=BE=C5=C5=B3=C9=C9=FD=D0=F2=CB=F9=D0=E8=B5=C4=D7=EE=C9=D9=BD=BB=BB=BB=B4=CE=
=CA=FD=A1=A3<BR><BR>SAMPLE OUTPUT (file=20
sort3.out)<BR>4</DIV>
<HR>
<P><STRONG>USACO 2.1.3 Sorting a Three-Valued=20
Sequence<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA1=B4=CE</STRONG></P>
=
<P><STRONG>=D2=D1=BE=AD=C1=AC=D0=F8=BA=C3=B6=E0=B4=CE1=B4=CEAC=C1=CB=A3=AC=
=D5=E6=C5=C2=D4=DA=D5=E2=D0=A9=CB=AE=CC=E2=C9=CF=C0=CB=B7=D1=CD=EARP=A1=A3=
<BR>=BD=AB=D5=E2=B8=F6=CA=FD=C1=D0=B7=D6=B3=C93=B2=BF=B7=D6=A3=AC=C5=C5=D0=
=F2=BA=F3=D3=A6=B8=C3=CA=C71=B5=C4=B2=BF=B7=D6=A3=AC=D3=A6=B8=C3=CA=C72=B5=
=C4=B2=BF=B7=D6=A3=AC=D3=A6=B8=C3=CA=C73=B5=C4=B2=BF=B7=D6=A1=A3<BR>=D5=E2=
3=B8=F6=B2=BF=B7=D6=C8=E7=B9=FB=D3=D0=CA=FD=B1=BE=C0=B4=B8=C3=D4=DA=B5=DA=
1=B2=BF=B7=D6=A3=AC=CF=D6=D4=DA=D4=DA=B5=DA2=B2=BF=B7=D6=A3=AC=CD=AC=CA=B1=
=D3=D0=CA=FD=B1=BE=C0=B4=B8=C3=D4=DA=B5=DA2=B2=BF=B7=D6=A3=AC=CF=D6=D4=DA=
=D4=DA=B5=DA1=B2=BF=B7=D6=A3=AC=D5=E2=D1=F9=D5=E2=C1=BD=B8=F6=CA=FD=BF=C9=
=D2=D41=B4=CE=BD=BB=BB=BB=C5=C5=BA=C3=D0=F2=A1=A3<BR>=C6=E4=D3=E03=B8=F6=CA=
=FD=C1=BD=B4=CE=BF=C9=D2=D4=C5=C5=BA=C3=D0=F2=A3=AC=C8=E7=D3=D02=B8=F6=CA=
=FD=B5=A5=B6=C0=B3=F6=C0=B4=A3=AC2=B4=CE=C5=C5=BA=C3=D0=F2=A1=A3</STRONG>=
</P>
<P><STRONG>{<BR>TASK:sort3<BR>LANG:PASCAL<BR>}<BR>program=20
sort3;<BR>var<BR> =
n,count:integer;<BR> =20
f:array[1..1000] of byte;<BR> =
a,b,c,abc:array[1..3] of=20
integer;<BR>procedure init;<BR>var<BR> =20
i,x:integer;<BR>begin<BR> =20
assign(input,'sort3.in');reset(input);<BR> =20
readln(n);<BR> =20
fillchar(abc,sizeof(abc),0);<BR> =20
fillchar(a,sizeof(a),0);<BR> =20
fillchar(b,sizeof(b),0);<BR> =20
fillchar(c,sizeof(c),0);<BR> for i:=3D1 to n=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
readln(f[i]);<BR> &n=
bsp; =20
inc(abc[f[i]]);<BR> =20
end;<BR> for i:=3D1 to abc[1]=20
do<BR> =20
inc(a[f[i]]);<BR> for i:=3Di+1 to abc[2]+abc[1]=20
do<BR> =20
inc(b[f[i]]);<BR> for i:=3Di+1 to n=20
do<BR> =20
inc(c[f[i]]);<BR> =
close(input);<BR>end;<BR>function=20
min(x,y:integer):integer;<BR>begin<BR> if x>y =
then=20
exit(y)<BR> else exit(x);<BR>end;<BR>procedure=20
work;<BR>var<BR> =20
temp:integer;<BR>begin<BR> =20
assign(output,'sort3.out');rewrite(output);<BR> =20
count:=3D0;<BR> =20
temp:=3Dmin(a[2],b[1]);<BR> =20
dec(a[2],temp);<BR> =20
dec(b[1],temp);<BR> =20
inc(count,temp);<BR> =20
temp:=3Dmin(b[3],c[2]);<BR> =20
dec(b[3],temp);<BR> =20
dec(c[2],temp);<BR> =20
inc(count,temp);<BR> =20
temp:=3Dmin(a[3],c[1]);<BR> =20
dec(a[3],temp);<BR> =20
dec(c[1],temp);<BR> =20
inc(count,temp);<BR> =20
temp:=3Da[2]+a[3]+b[1]+b[3]+c[1]+c[2];<BR> =
inc(count,(temp=20
div 3)*2+temp mod 3);<BR> =20
writeln(count);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG>USACO =
=B5=C4=B7=D6=CE=F6=D7=EE=BF=EC=B5=C4O=A3=A8n=A3=A9=A3=AC=BA=CD=CE=D2=B5=C4=
=D2=BB=D1=F9=A1=A3</STRONG></P>
<P></P>
<P></P>
<P><STRONG>We read the input into an array, and sort a copy of it =
in=20
another array, so we know what we have and what we want. =
</STRONG></P>
<P><STRONG>A swap touches two elements, so it can correct at most =
two=20
misplaced elements. We run through the array looking for pairs of=20
misplaced elements that a swap would correct, and do those swaps.=20
</STRONG></P>
<P><STRONG>The remaining misplaced elements form little cycles: a =
1 where=20
a 2 should be, a 2 where a 3 should be, and that 3 where the 1 =
should be.=20
It takes two swaps to correct such a cycle. So we count the number =
of such=20
cycles (by counting misplaced elements and dividing by three) and =
then add=20
in two times that many swaps. </STRONG></P><PRE><STRONG>#include =
<stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 1000
int n;
int have[MAXN];
int want[MAXN];
int
intcmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
void
main(void)
{
int i, j, k, n, nn[4], nswap, nbad;
FILE *fin, *fout;
fin =3D fopen("sort3.in", "r");
fout =3D fopen("sort3.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d", &n);
for(i=3D0; i<n; i++) {
fscanf(fin, "%d", &have[i]);
want[i] =3D have[i];
}
qsort(want, n, sizeof(want[0]), intcmp);
/* swaps that correct two elements */
nswap =3D 0;
for(i=3D0; i<n; i++)
for(j=3D0; j<n; j++) {
if(have[i] !=3D want[i] && have[j] !=3D want[j]
&& have[i] =3D=3D want[j] && have[j] =3D=3D =
want[i]) {
have[i] =3D want[i];
have[j] =3D want[j];
nswap++;
}
}
/* remainder are pairs of swaps that correct three elements */
nbad =3D 0;
for(i=3D0; i<n; i++)
if(have[i] !=3D want[i])
nbad++;
assert(nbad%3 =3D=3D 0);
nswap +=3D nbad/3 * 2;
fprintf(fout, "%d\n", nswap);
exit(0);
}
</STRONG></PRE>
<P><STRONG>Dan Jasper from Germany writes: </STRONG></P>
<P><STRONG>The previous solution needs a copy of the original list =
and=20
O(N<SUP>2</SUP>) time. I think it was necessary with the original =
task,=20
where you had to print out the exchange operations, but to just =
count=20
them, there is a more efficient solution. You can count the "1", =
"2" and=20
"3", so you can calculate in what parts (buckets) of the list they =
have to=20
be. The rest of the solution is somehow equal to yours, but all in =
all it=20
uses O(N) time and does not need a copy of the list. =
</STRONG></P><PRE><STRONG>#include <stdio.h>
int list[1000], N, res, count[3], start[3];
in[3][3]; // this counts the number of "1"s in bucket "2", ...
void readFile() {
FILE *f; int i;
f =3D fopen("sort3.in", "r");
fscanf(f, "%d", &N);
for(i =3D 0; i < N; i++) {
fscanf(f, "%d", &list[i]);
}
fclose(f);
}
void writeFile() {
FILE *f;
f =3D fopen("sort3.out", "w");
fprintf(f, "%d\n", res);
fclose(f);
}
void findBuckets() {
int i;
for(i =3D 0; i < N; i++) count[list[i]-1]++;
start[0] =3D 0;
start[1] =3D count[0];
start[2] =3D count[0] + count[1];
}
void findWhere() {
int i, j;
for(i =3D 0; i < 3; i++) {
for(j =3D 0; j < count[i]; j++) in[list[start[i] + =
j]-1][i]++;
}
}
void sort() {
int h;
// 1 <-> 2
h =3D in[0][1];
if(in[1][0] < h) h =3D in[1][0];
res +=3D h; in[0][1] -=3D h; in[1][0] -=3D h;
// 3 <-> 2
h =3D in[2][1];
if(in[1][2] < h) h =3D in[1][2];
res +=3D h; in[2][1] -=3D h; in[1][2] -=3D h;
// 1 <-> 3
h =3D in[0][2];
if(in[2][0] < h) h =3D in[2][0];
res +=3D h; in[0][2] -=3D h; in[2][0] -=3D h;
// Cycles
res +=3D (in[0][1] + in[0][2]) * 2;
}
void process() {
findBuckets();
findWhere();
sort();
}
int main () {
readFile();
process();
writeFile();
return 0;
}
</STRONG></PRE>
<P><STRONG>Bulgaria's Evgeni Dzhelyov writes: </STRONG></P>
<P><STRONG>I read the elements one by one and count them, so we =
know=20
exactly how 1s, 2s and 3s we have and we know how the sorted array =
looks=20
like. Then I count the 2s in 1 and 1s in 2, so it is obvious that =
we need=20
min(2sin1, 1sin2) swaps, I do the same for 1-3 and 2-3. The sum of =
all=20
these mins give us the number of direct swaps we need. After that =
number=20
of swaps we would have N 1s, 2s and 3s and we would need 2*N =
swaps, where=20
N is max(2sin1, 1sin2) - min(2sin1, 1sin2). </STRONG></P>
<P><STRONG>Here is the source code: =
</STRONG></P><PRE><STRONG>#include <fstream>
using namespace std;
int min (int a, int b) { return a < b ? a : b; }
int max (int a, int b) { return a > b ? a : b; }
int main () {
int s[1024];
int n;
int sc[4] =3D {0};
=20
ifstream fin("sort3.in");
ofstream fout("sort3.out");
fin>>n;
for (int i =3D 0; i < n; i++) {
fin>>s[i];
sc[s[i]]++;
}
int s12 =3D 0, s13 =3D 0, s21 =3D 0, s31 =3D 0, s23 =3D 0, s32 =3D =
0;
for (int i =3D 0; i < sc[1]; i++){
if (s[i] =3D=3D 2) s12++;
if (s[i] =3D=3D 3) s13++;
}
=20
for (int i =3D sc[1]; i < sc[1]+sc[2]; i++){
if (s[i] =3D=3D 1) s21++;
if (s[i] =3D=3D 3) s23++;
}
=20
for (int i =3D sc[1]+sc[2]; i < sc[1]+sc[2]+sc[3]; i++){
if (s[i] =3D=3D 1) s31++;
if (s[i] =3D=3D 2) s32++;
}
=20
fout<<min(s12, s21)+min(s13, s31)+min(s23, s32) +
2*(max(s12, s21) - min(s12, s21))<<endl;
return 0;
}</STRONG></PRE>
<P></P></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
href=3D"http://hi.baidu.com/leokan/modify/blog/03feff1f625f3667f724e477">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/03feff1f625f3667f724e477.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3D03feff1f625f3667f724e477=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -