USACO 2012 December Contest Bronze 见面与问候 (模拟相遇问题)

题目描述

众所周知，奶牛是非常有社交礼貌的动物：每当两头奶牛分开后相遇，它们都会用友好的“哞哞”声互相问候。
奶牛贝茜和她的朋友艾希正在农夫约翰的农场中的一条很长的道路上散步。
我们可以将此道路视为一个一维数轴。
贝茜和艾希都从原点出发，以相同的速度（1 单位距离/单位时间）行走一段时间。
请根据每头奶牛的运动情况描述，确定它们相互打招呼的次数。
贝茜和艾希可以在不同的时间点停止移动，并且她们的移动时间都不会超过 1000000 单位。

输入格式

第一行包含两个整数 B 和 E。
接下来 B 行，描述了贝茜的移动。每行包含一个正整数后跟一个字符 L 或 R，表示贝茜沿某个方向（左或者右）移动了若干单位距离。
再接下来 E 行，描述了艾希的移动。每行包含一个正整数后跟一个字符 L 或 R，表示艾希沿某个方向（左或者右）移动了若干单位距离。

输出格式

输出她们相互打招呼的次数。
注意，在最初位于初始位置时，她们不打招呼。

数据范围
$1\le B,E\le 50000$

输入样例：

4 5
3 L
5 R
1 L
2 R
4 R
1 L
3 L
4 R
2 L

输出样例：

3

分析

用一个集合找到所有输入的时间点，之后求出该时刻二者的方位，最后遍历同一时刻a、b的方位进行比较。

C++代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int n,m,x,ans;
set<int> se;
char op;
PII opa[50010],opb[50010];
int main()
{
    se.insert(0);
    cin>>n>>m;
    int t=0,ma=-1;
    for(int i=0;i<n;i++)
    {
        cin>>x>>op;
        t+=x;
        int speed=1;
        //往左走的话速度为负数
        if(op=='L') speed=-1;
        opa[i]={t,speed};
        //集合插入所有时间刻
        se.insert(t);
    }
    t=0;
    for(int i=0;i<m;i++)
    {
        cin>>x>>op;
        t+=x;
        int speed=1;
        if(op=='L') speed=-1;
        opb[i]={t,speed};
        //集合插入所有时间刻
        se.insert(t);
    }
    
	//插入一个右边界
    opa[n]={2000001,0};
    opb[m]={2000001,0};
    int a[100010],b[100010],idx1=0,idx2=0;
    int i=0,pre;
    for(auto x:se)
    {
        if(!x){
            pre=0;
            a[i]=0,b[i]=0;
        }
        else{
        	//求出该时刻a、b的位置
            while(x>opa[idx1].first) idx1++;
            int speed=opa[idx1].second;
            a[i]=a[i-1]+(x-pre)*speed;
            
            while(x>opb[idx2].first) idx2++;
            speed=opb[idx2].second;
            b[i]=b[i-1]+(x-pre)*speed;
        }
        pre=x;
        i++;
    }
    
    for(int j=1;j<i-1;j++)
    {
    	//该时刻a在b后边但下一刻a在b前边，二者相遇
        if(a[j]<b[j]){
            if(a[j+1]>=b[j+1]) ans++;
        } //该时刻a在b前边但下一刻a在b后边，二者相遇
        else if(a[j]>b[j]){
            if(a[j+1]<=b[j+1]) ans++;
        }

    }
    cout<<ans;
    return 0;
}