2.1　直叙式模拟

直叙式模拟就是要求编程者按照试题给出的规则或求解过程，直接进行模拟。这类试题不需要编程者设计精妙的算法来求解，但需要编程者认真审题，不要疏漏任何条件。

由于直叙式模拟只需严格按照题意要求模拟过程即可，因此大多属于简单模拟题。当然，并非所有直叙式模拟题都属于简单模拟题，关键是看模拟对象所包含的动态变化的属性有多少。动态属性越多，难度越大。

【2.1.1　Speed Limit】

Bill和Ted踏上行程，但他们汽车的里程表坏了，因此他们不知道驾车走了多少英里 1英里=1609.344米。——编辑注。幸运的是，Bill有一个正在运行的跑表，可以记录他们的速度和驾驶了多少时间。然而，这个跑表的记录方式有些古怪，需要他们计算总的驾驶距离。请编写一个程序完成这项计算。

例如，他们的跑表显示如下：

这表示开始的2小时他们以20英里的时速行驶，然后的6-2=4小时他们以30英里的时速行驶，再以后的7-6=1小时他们以10英里的时速行驶，所以行驶的距离是2×20+4×30+1×10=40+120+10=170英里。总的时间耗费是从他们旅行开始进行计算的，而不是从跑表计数开始计算的。

输入

输入由一个或多个测试用例组成。每个测试用例开始的第一行为一个整数n（1≤n≤10），后面是n对值，每对值一行。每对值的第一个值s是时速，第二个值t是总的耗费时间。s和t都是整数，1≤s≤90且1≤t≤12。t的值总是增序。n的值为-1表示输入结束。

输出

对于每一个数据集合，输出行驶距离，然后是空格，最后输出单词“miles”。

试题来源：ACM Mid-Central USA 2004

在线测试：POJ 2017，ZOJ 2176，UVA 3059

试题解析

本题是一道十分简单的直叙式模拟题，计算过程就是模拟跑表的运行来计算总里程：若上一个记录的驾驶时间为z，当前记录的速度为x、驾驶时间为y，则当前驾驶的距离为(y-z)×x，将该距离累计入总里程ans。

参考程序

#include <iostream>                      //预编译命令
using namespace std;                     //使用 C++标准程序库中的所有标识符
int main( )                              //主函数
{                                        //主函数开始
    int n, i, x, y, z, ans;              //声明整型变量n、i、x、y、z、ans
                                         // 多个测试用例，每次循环处理一个
    while (cin >> n, n > 0)              //反复输入当前组的数据对数，直至输入结束
    {
        ans = z = 0;
        // 模拟跑表运行来计算
        for (i = 0; i < n; i++)          //输入和计算当前测试用例
        {
            cin >> x >> y;               //输入当前时速和总耗费时间
            ans += (y - z) * x;          //累计总里程
            z = y;                       //记下当前总耗费时间
        }
        cout << ans << "miles" << endl;  //输出当前数据组的总里程
    }
    return 0;
}

【2.1.2　Ride to School】

北京大学的许多研究生都住在万柳校区，距离主校区——燕园校区有4.5公里。住在万柳的同学或者乘坐巴士，或者骑自行车去主校区上课。由于北京的交通情况，许多同学选择骑自行车。

假定除Charley以外，所有的同学从万柳校区到燕园校区都以某个确定的速度骑自行车。Charley则有一个不同的骑车习惯——他总是要跟在另一个骑车同学的后面，以免一个人独自骑车。当Charley到达万柳校区的大门口的时候，他就等待离开万柳校区去燕园校区的同学。如果他等到这样的同学，他就骑车跟着这位同学；如果没有这样的同学，他就等待去燕园校区的同学出现，然后骑车跟上。在从万柳校区到燕园校区的路上，如果有骑得更快的同学超过了Charley，他就离开原先他跟着的同学，加速跟上骑得更快的同学。

假设Charley到万柳校区大门口的时间为0，给出其他同学离开万柳校区的时间和速度，请你给出Charley到达燕园校区的时间。

输入

输入给出若干测试用例，每个测试用例的第一行为N（1≤N≤10000），表示除Charley外骑车同学的数量。以N=0表示输入结束。每个测试用例的第一行后面的N行表示N个骑车同学的信息，形式为：

Vi[空格]Ti

Vi是一个正整数，Vi≤40，表示第i个骑车同学的速度（kph，每小时公里数），Ti则是第i个骑车同学离开万柳校区的时间，是一个整数，以秒为单位。在任何测试用例中总存在非负的Ti。

输出

对每个测试用例输出一行：Charley到达的时间。在处理分数的时候进1。

试题来源：ACM Beijing 2004 Preliminary

在线测试：POJ 1922，ZOJ 2229

试题解析

本题没有数学公式和规律，通过直接模拟每个同学去往燕园校区的情景，得出Charley从万柳校区到燕园校区的时间。所以对每个测试用例，从Charley到万柳校区大门的时间0开始计时，求出每个同学到达燕园校区所用的时间，最少的时间就是Charley从万柳校区大门到燕园校区的时间。

设前i-1个同学中最早到达燕园校区的时间为min；第i个同学的车速为v，离开万柳校区的时间为t，则该同学到达燕园校区的时间。若x<min，则调整min为x。显然，按照这一方法依次计算所有同学的到达时间，最后得出的min即Charley到达的时间。

需要提醒的是，本题测试用例中有一个陷阱：当Ti取负值时，对于Charley到达燕园校区的时间没有影响，应予剔除。

参考程序

#include <iostream>                   //预编译命令
#include <cmath>
using namespace std;                  //使用 C++标准程序库中的所有标识符
int main()                            //主函数
{ 
    const double DISTANCE = 4.50;     //定义两个校区的距离
    while(true)                       //循环处理每个测试用例
    {
        int n;                        //定义整型变量n
        scanf("%d", &n);              //输入除Charley外的骑车同学数
        if (n == 0) break;            //若输入结束，则退出
        double v, t, x, min = 1e100;  //定义双精度实数v、t、x，min初始化为10100
        for(int i = 0; i < n; ++i)    //循环处理组内的每个骑车同学
        {
            scanf("%lf%lf", &v, &t);  //输入第i个骑车同学的速度和离开万柳校区的时间，计
                                      //算该同学到达燕园校区的时间x。若小于min，则min
                                      //调整为x
            if (t >= 0 && (x = DISTANCE * 3600 / v + t) < min)
            min = x;
        }
        printf("%.0lf\n", ceil(min)); //输出Charley到达的时间
    }
    return 0;
}

[1] 1英里=1609.344米。——编辑注

上一章目录下一章