求全国信息学奥林匹克联赛复赛普及组满分程序

NOIP 2007 普及组解题报告

1．奖学金

(scholar.pas／c／cpp)

问题描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数：学号、总分)是：

7 279

5 279

这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和)，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是：

5 279

7 279

则按输出错误处理，不能得分。

输入

输入文件scholar.in包含行n+1行：

第l行为一个正整数n，表示该校参加评选的学生人数。

第2到年n+l行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1～n(恰好是输入数据的行号减1)。

所给的数据都是正确的，不必检验。

输出

输出文件scholar.out***有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。

输入输出样例l

scholar.in scholar.out

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98 6 265

4 264

3 258

2 244

1 237

输入输出样例2

scholar.in scholar.out

80 89 89

88 98 78

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98 8 265

2 264

6 264

1 258

5 258

限制

50％的数据满足：各学生的总成绩各不相同

100％的数据满足：6<=n<=300

试题分析

简单的排序。因为n<=300，所以选择排序不会超时。

存储方面只需存储三个数：学好、语文成绩和总分。

参考程序

program a1(input,output);

var

n,x,y,z,i,j:integer;

a:array[1..300,1..3] of integer;

procedure swap(var a,b:integer); {交换过程}

var

s:integer;

begin

s:=a;

a:=b;

b:=s;

end;

begin

assign(input,'scholar.in');

assign(output,'scholar.out');

reset(input);

rewrite(output);

readln(n);

for i:=1 to n do

begin

readln(x,y,z);

a[i,1]:=i;

a[i,2]:=x;

a[i,3]:=x+y+z;

end;

for i:=1 to n-1 do {选择排序}

for j:=i+1 to n do

if (a[i,3]<a[j,3]) or ((a[i,3]=a[j,3]) and (a[i,2]<a[j,2])) or ((a[i,1]>a[j,1]) and (a[i,3]=a[j,3]) and (a[i,2]=a[j,2])) then

begin

swap(a[i,1],a[j,1]);

swap(a[i,2],a[j,2]);

swap(a[i,3],a[j,3]);

end;

for i:=1 to 5 do

writeln(a[i,1],' ',a[i,3]);

close(input); {文件不要忘记关闭}

close(output);

end.

2．纪念品分组

(group.pas／c／cpp)

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入

输入文件group.in包含n+2行：

第1行包括一个整数w，为每组纪念品价格之和的上限。

第2行为一个整数n，表示购来的纪念品的总件数。

第3～n+2行每行包含一个正整数pi(5<=pi<=w)，表示所对应纪念品的价格。

输出

输出文件group.out仅一行，包含一个整数，即最少的分组数目。

输入输出样例

group.in group.out

100

90 6

限制

50％的数据满足：l<=n<=15

100％的数据满足：1<=n<=30000，80<=w<=200

试题分析

贪心法，先排序，然后按以下贪心策略：

设s为所需的组数。i,j为两个指针，开始时指向头和尾。

1．如果a[i]+a[j]<=w，s=:s+1，i:=i+1，j:=j-1。

2．如果a[i]+a[j]>w，s:=s+1，j:=j-1。

因为n<=300000,所以用选择排序可能会超时，最好用快速排序。

参考程序1

program a2_1(input,output);

var

a:array[1..30000] of integer;

w,n,i,j,s:integer;

procedure qsort(h,t:integer);

var

p,i,j:integer;

begin

i:=h;

j:=t;

p:=a[i];

repeat

while (a[j]>p) and (j>i) do j:=j-1;

if j>i then

begin

a[i]:=a[j];

i:=i+1;

while (a[i]<p) and (i<j) do i:=i+1;

if i<j then

begin

a[j]:=a[i];

j:=j-1;

end;

until i=j;

a[i]:=p;

i:=i+1;

j:=j-1;

if i<t then qsort(i,t);

if j>h then qsort(h,j);

end;

begin

assign(input,'group.in');

assign(output,'group.out');

reset(input);

rewrite(output);

readln(w);

readln(n);

for i:=1 to n do readln(a[i]);

qsort(1,n); {快速排序}

i:=1;

j:=n;

s:=0;

while i<=j do {贪心法}

begin

if i=j then

begin

s:=s+1;

break;

end;

if a[i]+a[j]<=w then

begin

i:=i+1;

j:=j-1;

s:=s+1;

end;

if a[i]+a[j]>w then

begin

s:=s+1;

j:=j-1;

end;

writeln(s);

close(input);

close(output);

end.

深入思考

快速排序的程序比较难编，是否能有一种比较好编得排序方法呢？答案是肯定的。设p数组的下标为5至200，每读入一个数字x，就将p[x]加1，这样数字全部读入后就是有序的了，效率甚至比快速排序还高。这样的话贪心部分也要有所改变。

参考程序2

program a2_2(input,output);

var

p:array[5..200] of integer;

x,i,w,n,j,s:integer;

begin

assign(input,'group.in');

assign(output,'group.out');

reset(input);

rewrite(output);

readln(w);

readln(n);

for i:=5 to 200 do p[i]:=0; {数组清0}

for i:=1 to n do {读入数据}

begin

readln(x);

p[x]:=p[x]+1;

end;

i:=5;

j:=200;

s:=0;

while i<=j do {贪心法}

begin

while p[i]=0 do i:=i+1; {找到不为空的数据}

while p[j]=0 do j:=j-1;

if i>j then break;

if i=j then {处理i=j的情况}

if i*2<=w then

begin

while p[i]>=2 do

begin

p[i]:=p[i]-2;

s:=s+1;

end;

s:=s+p[i];

end

else

s:=s+p[i];

if i+j<=w then {处理i+j<=w的情况}

if p[i]>p[j] then

begin

s:=s+p[j];

p[i]:=p[i]-p[j];

p[j]:=0;

end

else

begin

s:=s+p[i];

p[j]:=p[j]-p[i];

p[i]:=0;

end;

if i+j>w then {处理i+j>w的情况}

begin

s:=s+p[j];

p[j]:=0;

end;

writeln(s);

close(input);

close(output);

end.

3、守望者的逃离

(escape.pas/c/cpp)

问题描述

恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T。你的任务写写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且每次活动的持续时间为整数秒。距离的单位为米(m)。

输入

在输入文件escape.in仅一行，包括空格隔开的三个非负整数M,S,T。

输出

在输出文件escape.out包括两行：

第1行为字符串“Yes”或“No”（区分大小写），即守望者是否能逃离荒岛。

第2行包含一个整数。第一行为“Yes”（区分大小写）时表示守望者逃离荒岛的最短时间；第一行为“No”（区分大小写）时表示守望者能走的最远距离。

输入输出样例1

escape.in escape.out

39 200 4 No

197

输入输出样例1

escape.in escape.out

36 255 10 Yes

限制

30%的数据满足：1<=T<=10,1<=S<=100

50%的数据满足：1<=T<=1000,1<=S<=10000

100%的数据满足：1<=T<=300000,0<=M<=1000,1<=S<=108.

试题分析

典型的动态规划。

设f[i,j]为第i秒，魔法值为j时可行的最大距离。

f[i,j]:=max{f[i-1,j]+17,f[i-1,j-10]+60,f[i-1,j+4]} (当j≥10时);

f[i,j]:=max{f[i-1,j]+17,f[i-1,j+4]} (当j<10时)

按题目所说，最大魔法值为1000，最大时间为300000秒，那么需要300000000的数组，空间会溢出，所以使用两个一维数组来迭代，只需2000的数组，但是时间复杂度为O(t*m)，有可能会超时。

参考程序1

program a3(input,output);

var

a,b:array[0..10000]of longint;

m,s,t,i,j:longint;

function max(a,b,c:longint):longint; {三个数找最大值}

var

k:longint;

begin

if a>b then k:=a else k:=b;

if k<c then k:=c;

max:=k;

end;

begin

assign(input,'escape.in');

assign(output,'escape.out');

reset(input);

rewrite(output);

readln(m,s,t);

for i:=0 to 10000 do {数组清0}

begin

a[i]:=0;

b[i]:=0;

end;

for i:=1 to t do

begin

for j:=0 to 9 do

begin

b[j]:=max(a[j]+17,a[j+4],0); {动态规划}

if b[j]>=s then

begin

writeln('Yes'); {找到最小解，提前退出}

writeln(i);

close(input);

close(output);

halt;

end;

for j:=10 to m do

begin

b[j]:=max(a[j]+17,a[j+4],a[j-10]+60); {动态规划}

if b[j]>=s then

begin

writeln('Yes'); {找到最小解，提前退出}

writeln(i);

close(input);

close(output);

halt;

end;

a:=b;

end;

writeln('No'); {无解}

writeln(a[m]);

close(input);

close(output);

end.

{注：此程序两个点超时}

深入思考

前面的动态规划时间复杂度太高，是否能想出更优的算法呢？思考一下，可以发现，中间的过程无非就是闪烁加恢复魔法，有时再走几步，我们用ms数组记录，闪烁加恢复魔法可走的最大距离，再和走路比较，选出最优方案，存入ts数组，这样的话，时间复杂度只有O(t),比前面的算法好得多。

参考程序2

program a3_2(input,output);

var

m,s,t,ti:longint;

ms:array[1..2,0..300000] of longint;

ts:array[0..300000] of longint;

begin

assign(input,'escape.in');

assign(output,'escape.out');

reset(input);

rewrite(output);

readln(m,s,t);

ms[2,0]:=m;

ts[0]:=0;

for ti:=1 to t do {动态规划}

begin

if ms[2,ti-1]>=10 then {如果能使用闪烁，就是用}

begin

ms[1,ti]:=ms[1,ti-1]+60;

ms[2,ti]:=ms[2,ti-1]-10;

end

else

begin

ms[1,ti]:=ms[1,ti-1]; {恢复魔法值}

ms[2,ti]:=ms[2,ti-1]+4;

end;

if ts[ti-1]+17>ms[1,ti] then ts[ti]:=ts[ti-1]+17 else ts[ti]:=ms[1,ti]; {找出大的值}

if ts[ti]>=s then {如果顺利逃出，输出结果}

begin

writeln('Yes');

writeln(ti);

close(input);

close(output);

halt;

end;

writeln('No'); {无法逃出，输出结果}

writeln(ts[t]);

close(input);

close(output);

end.

{此程序所有测试点全部通过}

4．Hanoi双塔问题

(hanoi.pas/c/cpp)

问题描述

给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，***有n个不同的尺

寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘足不加区分的(下图为n=3的情形)。现要将

这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：

(1)每次只能移动一个圆盘；

(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序；

任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。

输入

输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。

输出

输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。

输入输出样例1

hanoi.in hanoi.out

1 2

输入输出样例2

hanoi.in hanoi.out

2 6

限制

对于50％的数据，1<=n<=25

对于100％的数据，l<=n<=200

提示

设法建立An与An-1的递推关系式。

试题分析

不难发现：

An=2An-1+2（特别的，A1=2）

证明如下：

要将A柱上的2n个盘子移到C柱上，最佳的策略就是先将(2n-2)个盘子借助C柱移到B柱上，所需的次数为An-1，再将A柱上最大的两个盘子直接移到C柱上，所需的次数为2，最后将B柱上的(2n-2)个盘子借助A柱移到C柱上，所需的次数为An-1。总次数An=An-1+2+An-1=An=2An-1+2。

进而，可以得出：

An=2n+1-2

然后使用高精度计算。

参考程序

program a4(input,output);

var

n,i,j:integer;

a:array[1..100] of 0..9;

procedure ppp(k:integer); {高精度计算2n+1}

var

i,j,w,s:integer;

begin

a[1]:=1;

w:=0;

for i:=1 to k do

for j:=1 to 100 do

begin

s:=a[j]*2+w;

a[j]:=s mod 10;

w:=s div 10; {进位}

end;

begin

assign(input,'hanoi.in');

assign(output,'hanoi.out');

reset(input);

rewrite(output);

readln(n);

ppp(n+1);

if a[1]>=2 then {减2的处理}

a[1]:=a[1]-2

else

begin

a[1]:=a[1]+8;

a[2]:=a[2]-1;

end;

i:=100;

while a[i]=0 do i:=i-1; {计算位数}

for j:=i downto 1 do write(a[j]); {反序输出}

writeln;

close(input);

close(output);

end.

By zhousi