题目描述
AcWing 1995. 见面与问候
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int b[N];
int n ,m;
int main()
{
int ci = 1,cj = 1;
cin >> n >> m;
int d;
char c;
while(n--)
{
cin >> d >> c;
if(c == 'L'){
for(int i = 1; i <= d ;i++){
a[ci] = a[ci-1]-1;
ci++;
}
}
else{
for(int i = 1; i <= d ;i++){
a[ci] = a[ci-1]+1;
ci++;
}
}
}
while(m--)
{
cin >> d >> c;
if(c == 'L'){
for(int i = 1; i <= d ;i++){
b[cj] = b[cj-1]-1;
cj++;
}
}
else{
for(int i = 1; i <= d ;i++){
b[cj] = b[cj-1]+1;
cj++;
}
}
}
//判断每个时间点,是否相遇
int sum = 0;
for(int i = 1;i < ci || i < cj;i++)
{
if(i < ci && i >=cj){
if(a[i] == b[cj-1]) sum++;
}
if(i < cj && i >=ci){
if(a[ci-1] == b[i]) sum++;
}
if( i < ci && i < cj){
if(a[i] == b[i] &&a[i-1]!= b[i-1])
sum++;
}
}
cout << sum;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla