屠夫和狼

屠夫和狼

时间： 1ms        内存：128M

描述：

一屠晚归，担中肉尽，止有剩骨。途经洞穴，歘一狼来，瞰担中肉，似甚垂涎。屠夫Vp m/s 匀速逃跑，狼在发现屠夫t 秒后以Vd m/s 匀速追赶，每当狼即将追上屠夫时，屠夫会向狼扔一块骨头，狼在发现骨头后立即将其捡起，以相同的速度匀速返回洞穴并花费f秒将骨头藏好，然后以相同的速度继续追赶屠夫。
假如洞穴离屠夫的住处距离为c 米，则屠夫担中至少有多少块骨头才能保证屠夫安全回家？假设狼恰好在屠夫到达住处时追上，则不需要投骨。

输入：

第一行给出整数T( 0 < T < 100)表示有T 组测试数据，每组测试数据包含5个整数vp,vd, t, f ,c, (1 ≤ vp ,vd ≤ 100, 1 ≤ t, f ≤ 10, 1 ≤ c ≤ 1000)。

输出：

每组测试数据单行输出最少所需的骨头数。

示例输入：

2
1 2 1 1 10
1 2 1 1 8

示例输出：

2
1

提示：

参考答案（内存最优[748]）：

#include <stdio.h>
#include <stdlib.h>
int main()
{
     float x,y,p,s;
     int m,i,n;
     float vp,vd,t,f,c;
     scanf("%d",&n);
     for(i=0;i<n;i++)
     {
         scanf("%f%f%f%f%f",&vp,&vd,&t,&f,&c);
         m=0;
         s=vp*t;
         if(vd<=vp)
         {
             printf("%d\n",m);
             continue;
         }
         x=s/(vd-vp);
         p=s+vp*x;
         if(p<c)
            m++;
        p+=(vp*x+vp*f);
         while(p<c)
         {
             y=p/(vd-vp);
             p+=y*vp;
             if(p<c)
                m++;
            p+=(f*vp+vp*y);
         }
         printf("%d\n",m);
     }
     return 0;
}

参考答案（时间最优[0]）：

#include <string>
#include <stdio.h>

int main(){
    int n;
    scanf("%d", &n);
    while( n -- ){
        int vd, vp, f, c;
        double t;
        scanf("%d%d%lf%d%d", &vp, &vd, &t, &f, &c);
        double ts = (double)c / vp;
        int cnt = 0;
        ts -= t;
        if (vd > vp)
        while (ts){
            double dt = vp * t / (vd - vp);
            if (ts > dt){
                cnt ++;
                t = t + dt * 2 + f;
                ts = ts - 2 * dt - f;
            }
            else
                break;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。