CF278A 题解
这题既然没有pascal题解,那我就来一篇
题目描述:
有 $n$ 个车站排成一个环形,给定 $n$ 个车站之间的距离,求从第$s$个车站到第 $t$ 个车站所需的最短距离。
题目分析:
也就是说,有一个这样的车站:
他可以这样走:
也可以这样走:
现在告诉你:
- ① 和 ② 的距离为 2
- ② 和 ③ 的距离为 3
- ③ 和 ④ 的距离为 1
- ④ 和 ① 的距离为 8
也就是下面这种状况:
那有的人就想,我只要判断出那个路线距离短就可以了呀,那么请看下面:
你要从 ① 走到 ④,你会怎么走?
- 是从 ① –> ② –> ③ –> ④
- 还是 ① –> ④
很明显,当然是 ① –> ② –> ③ –> ④ 要短一点,所以,路线短不一定距离短,好了,既然理解了题目和易错点,就要开始写程序了
做法分析:
我们先用一个数组,把每个点之间的距离存下来,然后计算总路程
read(n);
for i:=1 to n do
begin
read(f[i]);
sum:=sum+f[i];//计算总路程
end;
然后输入 $s$ , $t$ 并且将小的放在前面
if s>t then //如果s大于t,就将他们交换过来
begin
q:=s; //交换
s:=t;
t:=q;
end;
再计算从 $s$ 到 $t$ 的路线距离,这时候可能有人问:不是要计算两条吗?
计算两条当然是可以的,但是我们之前已经计算了总长度,所以说,总长度 减去 $s$ 到 $t$ 的路线距离 就等于 另一条路线长度。
for i:=s to t-1 do
k:=k+f[i];
最后,只要一个判断输出,就可以了
if k<(sum-k) then
writeln(k)
else
writeln(sum-k);
下面是完整代码:
var n,s,t,sum,k,i,q:longint;
f:array [1..102] of longint;
Begin
read(n);
for i:=1 to n do
begin
read(f[i]);
sum:=sum+f[i];
end;
read(s,t);
if s>t then
begin
q:=s;
s:=t;
t:=q;
end;
for i:=s to t-1 do
k:=k+f[i];
if k<(sum-k) then
writeln(k)
else
writeln(sum-k);
end.
希望本题解对大家有帮助,也感谢管理员百忙之中帮我审核题解,谢谢!
End.