题解 P1568 【赛跑】

· · 题解

话说第一次写题解实在激动

本题思路

首先读入n和m，然后读入SH的速度vn[i]和持续时间tn[i]，之后读入KC的速度vm[i]和持续时间tm[i]，但是在读入KC数据的同时，我们便开始处理数据，大概思路就是定义两个变量wn = 0, wm = 0来存储两个人分别已经跑过的距离，然后比较，如果wn-wm的符号改变了，那么ans++。其他的细节请看下面的代码注释。

代码+细节解释

#include<cstdio>
using namespace std;
int n, m, wn = 0, wm = 0, vn[1001], tn[1001], vm[1001], tm[1001];
//wn:SH已经跑过的距离，wm:KC已经跑过的距离
//vn[]/vm[]:SH和KC的移动速度
//tn[]/tm[]:SH和KC移动速度的持续时间
int nt = 1, mt = 1, z = -1, ans = -1;
//nt:当前使用哪个vn[]的值,mt:当前使用哪个vm[]的值
//z:是谁领先(1:KC领先 0:SH领先)
//可以通过看z是否改变来判断是否改变
//ans:改变次数
//为什么ans初始值是-1？
//因为z的初始值是-1，即两个人都没有领先，
//然后在跑步过程中，肯定会有某个人开始领先，这时候并没有改变顺序，
//但是ans仍然要+1，为了解决这一问题，将ans初始值置-1。
int work(int x)
//返回x的符号，这里的x是SH和KC距离之差（见下面定义s那行）
//如果大于0返回1，如果小于0返回0，如果等于0返回z的值
//返回z的值的原因：
//因为当距离相等的时候，没法决定返回0还是1，这时候还没有谁超过谁，
//并且我们我们不知道在距离差距不为0的时候是谁领先，所以直接返回z，
//即返回上一个状态
{
    if (x > 0)return 1;
    else if (x == 0)return z;
    return 0;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &vn[i], &tn[i]);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &vm[i], &tm[i]);
        while (mt <= i)//mt>i的情况还没有读入
        {
            if (tm[mt] == 0 && mt <= m + 1)
            {
                mt++;//如果这个速度的持续时间用完了，就将mt++
                continue;
                //一定要加上面一行，这可以保证mt>i，否则会导致“越界”
                //不是真的越界，只是还没有读入
            }
            if (tn[nt] == 0 && nt <= n + 1)nt++;//和上面一样的道理
            wm += vm[mt];
            tm[mt]--;
            wn += vn[nt];
            tn[nt]--;
            //距离+vm/vn，时间-1
            int s = wm - wn;//计算距离的差
            if (work(s) != z)//如果领先程度改变，则ans++
            {
                ans++;
                z = work(s);
            }
        }
    }
    if (ans == -1)ans = 0;
    //如果距离一直相等，会导致ans一直没有改变，这里将ans置0
    printf("%d", ans);
    return 0;
}