信息学2014年第六题安装饮水机

NHOI2014小学甲组题

2014年南海区青少年信息学奥林匹克竞赛试题

第六题 安装饮水机(post)

问题描述

为倡导城市低碳生活，市文明办计划举办马拉松比赛，为确保比赛安全，沿途设置了一些观察点。每个观察点派一个观察员驻守。由于天气比较炎热，需要在沿途安装一些饮水机，使得观察员可以去取水喝。由于观察员每移动一个单位的路程，需要耗费一个单位的体力。而每个观察员的体力有限，只能在他体力能支持的范围内去取水喝，要不他就会渴死或累死。

聪明的楠楠也参与了这次比赛的筹备工作。他的任务是设计一个理想的安装饮水机方案，使得安装的饮水机最少，但又保证所有观察员都能取到水喝。 输入格式：

输入数据有若干行。。

第一行，仅一个整数，表示有N(0

接下来有N行，每行两个整数S(0

输出最少要安装几台饮水机。 输入样例：

4

6 3 12 2 1 5 14 5 输出样例：

2

样例说明：他可以将饮水机安装在距离起点为6和12的位置上，这样所有的观察员都能喝到水。方案有多种，只需输出最少需要几台饮水机即可。

参考程序：（韩保红）

var n,i,j,m:integer;s,w:longint;a,b:array [1..1000] of longint; f:array [1..1000] of boolean; begin

assign(input,'post.in');reset(input);

第 1 页 共 2 页

NHOI2014小学甲组题

assign(output,'post.out');rewrite(output); readln(n); for i:=1 to n do begin

readln(s,w); a[i]:=s-w;b[i]:=s+w; end;

for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then begin

s:=a[j];a[j]:=a[i];a[i]:=s; w:=b[j];b[j]:=b[i];b[i]:=w; end;

for i:=1 to n do if not f[i] then begin

s:=a[i];w:=b[i]; for j:=i+1 to n do if w>=a[j] then begin

f[j]:=true;

if a[j]>s then s:=a[j]; if b[j]

writeln(m);

close(input);close(output); end.

第 2 页 共 2 页