题解 P1011 【车站】

小古比鱼 · 2016-11-19 16:54:52 · 题解

程序截图与运行结果：http://lvyanchao0.blog.163.com/album/#m=2&aid=273239275&pid=9712085137

# include <stdio.h>
int on[19],off[19]={0},train[20];                    //火车在各站上下车的人数分别为on和off
void station(int stop)                                //火车在中途某些站stop停靠时
{
    on[stop]=on[stop-1]+on[stop-2];                    //各站上车的人数为前两站上车的人数之和
    off[stop]=on[stop-1];                            //各站下车的人数为上一站上车的人数
    train[stop]=train[stop-1]+on[stop]-off[stop];    //火车在离开各站时的人数为train
}
int main()
{
    int a,n,m,x,second;                                //火车共停靠n(n≤20)站，在起点站上车的人数为a(a≤20)
    scanf("%d %d %d %d",&a,&n,&m,&x);                //在终点站下车的人数为m(m≤2000)
    on[0]=train[0]=train[1]=a;                        //火车在第2站上下车的人数相等
    for(second=0;;++second)                            //假设火车在第2站上下车的人数均为second
    {
        on[1]=off[1]=second;
        for(a=2;a<n-1;a++)                            //火车在第3站至倒数第2站之间停靠时
            station(a);                                //各站上下车的人数由函数station来确定
        if(!(train[n-1]=train[n-2]-m))                //若火车在离开倒数第2站时的人数恰好为m，则second取值正确
            return !printf("%i\n",train[x-1]);        //此时输出火车在离开第x(x≤20)站时的人数，结束程序
    }                                                //否则使second增值，直到其取值正确为止
}

程序截图与运行结果：http://lvyanchao0.blog.163.com/album/#m=2&aid=273239275&pid=9712339044

# include <stdio.h>
int main()
{
    const S[]={0,1,2,4,7,12,20,33,54,88,143,232,376,609,986,1596,2583};       //S[n]为斐波那契数列的前n项和
    int a,n,m,x;                                                           //火车共停靠n(5≤n≤20)站，在起点站上车的人数为a(a≤20)
    scanf("%d %d %d %d",&a,&n,&m,&x);                                       //在终点站下车的人数为m(m≤2000)，在第2站上下车的人数相等
    return !printf("%i\n",S[x-3]*(m-(S[n-5]+2)*a)/S[n-4]+(S[x-4]+2)*a);       //输出火车在离开第x(4≤x＜n)站时的人数
}

//说明：火车在第3站至倒数第2站之间停靠时，各站上车的人数为前两站上车的人数之和，各站下车的人数为上一站上车的人数。
//解析：假设火车在第2站上下车的人数均为second，则second=(m-(S[n-5]+2)*a)/S[n-4]，火车在离开第x(4≤x＜n)站时的人数为S[x-3]*second+(S[x-4]+2)*a。