问题标题: 洛谷：P1011 车站

Question

0

已解决

王星河

资深光能

P1011 车站

酷町豆刷题求解 C++ 0条评论 6 年，8 月前

Answer 1

已采纳

陆麟瑞

资深天翼

设第二站上车b人,f[i]为每站上车人数

依题意得

f[1]=a f[2]=b f[3]=1b+a f[4]=2b+a f[5]=3b+2a f[6]=5b+3a ……

可以发现a,b系数为斐波那契数列

设fibo[]为斐波那契数列

fibo[]={1,1,2,3,5,8,13,21,34……}

则第i站上车人数(i>2)为

f[i]=fibo[i-1]*b+fibo[i-2]*a;

∵下车人数=上一站上车人数

∴中间的上下车不必模拟，没有意义，可以忽略

再者，终点站没有人上车

不难得出

m=f[n-1]+a-b

上一站上车+起始站人数-第二站上车的人数=最后下车的人数

然后求出b.

fibo[0]=0;fibo[1]=1;
    for(int i=2;i<=n;i++)
        fibo[i]=fibo[i-1]+fibo[i-2];
b=(m-(fibo[n-3]+1)*a)/(fibo[n-2]-1);
    printf("%d",(fibo[x-1]-1)*b+(fibo[x-2]+1)*a);

Answer 2

褚俊皓

新手天翼