上下车问题

[题目描述]

火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问x站开出时车上的人数是多少？

若无解则输出“No answer.”

[输入格式]

[输出格式]

输出一个数x即站开出时车上的人数

[输入样例]

1 6 7 3

[输出样例]

2

　　一道老题，非常简单，但仍有思考价值。这里简单说下两种方法。

方法一：枚举

　　枚举第二站上下车的人数，根据题目给出的递推关系判断是否正确。递推关系题目描述得很清晰，数据规模也完全没有问题。这是最易想到的解题思路，很基础，因此不贴代码了。

方法二：递推+简单计算

　　先来列一个表：

站：1    2    3     4       5      ……

总：a    a    2a    2a+k    3a+2k  ……

上：a    k    a+k   a+2k    2a+3k  ……

下：0    k    k     a+k     a+2k   ……

　　如果我们稍动脑筋分析一下，便不难得出第i站开出时车上的人数m[i]=in[1]+…+in[i-2]+a（i>=3，in[k]表示第k站上车的人数）。那么用fa[i]来表示第i站上车人数的a的系数，用fb[i]来表示第i站上车人数的k的系数，用数组suma和sumb分别表示从第一站到每一站的上车人数总和的a和k的系数，根据题意建立这些数组的递推关系。则有m=suma*a+sumb*k+a，因为已知a,m，所以便可轻松求出k的值，这样就能求出火车从任意站开出时的人数了。

　　讲得可能不大清楚，看我的代码吧。

var k:double;
    a,n,m,x,i,j:longint;
    fa,fb,suma,sumb:array[1..20]of longint;
begin
    readln(a,n,m,x);
    fa[1]:=1; fa[2]:=0; fb[1]:=0; fb[2]:=1;
    for i:=3 to n do begin
        fa[i]:=fa[i-1]+fa[i-2];
        fb[i]:=fb[i-1]+fb[i-2];
    end;
    suma[1]:=a; sumb[1]:=0;
    for i:=2 to n do begin
        suma[i]:=suma[i-1]+fa[i]*a;
        sumb[i]:=sumb[i-1]+fb[i];
    end;
    k:=(m-suma[n-3]-a)/sumb[n-3];
    if k-trunc(k)<1e-6 then writeln(suma[x-2]+sumb[x-2]*trunc(k)+a) else writeln('No answer.');
end.