题目描述
众所周知,奶牛是非常有社交礼貌的动物:每当两头奶牛分开后相遇,它们都会用友好的“哞哞”声互相问候。
奶牛贝茜和她的朋友艾希正在农夫约翰的农场中的一条很长的道路上散步。
我们可以将此道路视为一个一维数轴。
贝茜和艾希都从原点出发,以相同的速度(1 单位距离/单位时间)行走一段时间。
请根据每头奶牛的运动情况描述,确定它们相互打招呼的次数。
贝茜和艾希可以在不同的时间点停止移动,并且她们的移动时间都不会超过 1000000 单位。
样例
4 5
3 L
5 R
1 L
2 R
4 R
1 L
3 L
4 R
2 L
输出
3
算法1
(暴力枚举)
先比较两个人相同的部分,再比较长的部分和短的最后所在位置(题目要求)
-1 -2 -3 -2 -1 0 **1** 2 **1** 2 **3**
1 2 3 4 3 2 **1** 0 **1** 2 3 4 **3** 2 4
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50010;
vector<int> a,b;
int main()
{
int s1=0,s2=0;
int m,n;
cin >> m>>n;
while(m--)
{
int x;string op;
cin >> x >> op;
if(op=="L")
{
while(x--)
{
s1-=1;
a.push_back(s1);
}
}
else
{
while(x--)
{
s1+=1;
a.push_back(s1);
}
}
}
while(n--)
{
int x;string op;
cin >> x >> op;
if(op=="L")
{
while(x--)
{
s2-=1;
b.push_back(s2);
}
}
else
{
while (x -- )
{
s2+=1;
b.push_back(s2);
}
}
}
/* for (int i = 0; i < a.size(); i ++ ) cout << a[i]<<" ";
puts("");
for (int i = 0; i < b.size(); i ++ ) cout << b[i]<<" ";*/
int cnt=0;
for (int i = 0; i < min(a.size(),b.size())-1; i ++ )
{
if(a[i]!=b[i]&&a[i+1]==b[i+1]) cnt++;
}
//a短b长
if(a.size()<b.size())
{
for (int i = a.size(); i < b.size()-1; i ++ )
{
if(a[a.size()-1]!=b[i]&&a[a.size()-1]==b[i+1]) cnt++;
}
}
//b短a长
if(b.size()<a.size())
{
for (int i = b.size(); i < a.size()-1; i ++ )
{
if(b[b.size()-1]!=a[i]&&b[b.size()-1]==a[i+1]) cnt++;
}
}
cout << cnt;
return 0;
}