Meet and Greet

题目链接

• 题意：
  两个牛在一位坐标系上左右运动，速度相同，当两个牛相遇（之前不在一起，现在走到一起了）的时候会叫一声，现在问会叫几声
• 分析：
  有两种方法，自己反思优略：第一种，以牛的运动状态发生变化的时间点为界限，不用多说，麻烦，效率高；另一种，以时间为界限，简单，效率低
  自己做题时候也没想就按照第一种方法上了，结果一个多小时就这样过去了。。。由于题目告诉了每个牛动时间单位数在1e6以内，那么显然第二种方法是最好的。
• 总结：
  做题时候需要自己看题目的数据范围和情况以决定要使用的算法，不要一股脑就认为高效的算法一定是好的。（尤以枚举为甚）
  这种两个物体运动让模拟的需要多练习，编码能力还是不行

const int MAXN = 110000;

int num[2][MAXN], dir[2][MAXN];

void input(int n, int* tnum, int* tdir)
{
    char t;
    REP(i, n)
    {
        cin >> tnum[i] >> t;
        if (t == ‘L‘)
            tdir[i] = 0;
        else
            tdir[i] = 1;
    }
}

void Go(int& ind, int all, int& n, int& d, int& p, int& foot, int* tnum, int* tdir)
{
    if (ind >= all || n == INF)
        return;
    if (d == 0)
        p -= foot;
    else
        p += foot;
    n -= foot;
    if (n == 0)
    {
        if (++ind >= all)
        {
            n = INF;
            d = -1;
            return;
        }
        n = tnum[ind];
        d = tdir[ind];
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);
    int a, b;
    RII(a, b);
    input(a, num[0], dir[0]);
    input(b, num[1], dir[1]);

    int ia = 0, ib = 0, pa = 0, pb = 0, da = dir[0][0], db = dir[1][0], foot;
    int na = num[0][0], nb = num[1][0], ans = 0, Min;
    while (ia < a || ib < b)
    {
        foot = abs(pa - pb);
        if (pa == pb || da == db)
        {

        }
        else if (na == INF)
        {
            if (((pa < pb) != db) && (foot <= nb))
                ans++;
        }
        else if (nb == INF)
        {
            if (((pb < pa) != da) && (foot <= na))
                ans++;
        }
        else if (((pa < pb) == (da > db)) && (foot % 2 == 0) && (na >= foot / 2) && (nb >= foot / 2))
        {
            ans++;
        }
        Min = min(na, nb);
        Go(ia, a, na, da, pa, Min, num[0], dir[0]);
        Go(ib, b, nb, db, pb, Min, num[1], dir[1]);
    }
    cout << ans << endl;
    return 0;
}                                 

const int MAXN = 110000;


int n[2][MAXN];
int d[2][MAXN];

void input(int* num, int* dir, int n)
{
    char t;
    REP(i, n)
    {
        scanf("%d %c ", &num[i], &t);
        if (t == ‘L‘)
            dir[i] = -1;
        else
            dir[i] = 1;
    }
}

void move(int& ind, int& n, int& d, int& pre, int& all, int& p, int* num, int* dir)
{
    pre = p;
    if (ind == all)
        return;
    p += d;
    if (--n == 0)
    {
        ind++;
        n = num[ind];
        d = dir[ind];
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);
    int a, b;
    while (~RII(a, b))
    {
        input(n[0], d[0], a);
        input(n[1], d[1], b);
        int prea = 0, preb = 0, pa = 0, pb = 0;
        int na = n[0][0], nb = n[1][0], da = d[0][0], db = d[1][0], ia = 0, ib = 0;
        int ans = 0;
        while (ia < a || ib < b)
        {
            move(ia, na, da, prea, a, pa, n[0], d[0]);
            move(ib, nb, db, preb, b, pb, n[1], d[1]);
            if (prea != preb && pa == pb)
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

Meet and Greet,布布扣,bubuko.com

Meet and Greet

原文：http://blog.csdn.net/wty__/article/details/21184375