题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
蒟蒻写的又臭又长的代码
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
int b, e;
queue<pair<int, char> > bh;
queue<pair<int, char> > ah;
int main(){
cin >> b >> e;
char s;
int n;
while( b -- ){
cin >> n >> s;
bh.push({n, s});
}
while( e -- ){
cin >> n >> s;
ah.push({n, s});
}
int nob = 0, noa = 0, res = 0;
while( !ah.empty() && !bh.empty() ){
pair<int, char> bb = bh.front();
pair<int, char> aa = ah.front();
int tb = bb.first, ta = aa.first;
char fb = bb.second, fa = aa.second;
int t = min(tb, ta);
if( tb < ta ){
bh.pop();
ah.front().first = ta - tb;
}
else if( ta < tb ){
ah.pop();
bh.front().first = tb - ta;
}
else{
bh.pop(), ah.pop();;
}
int neb, nea;
if( fb == 'L' ) neb = nob - t;
else neb = nob + t;
if( fa == 'L' ) nea = noa - t;
else nea = noa + t;
if( nob < noa && neb >= nea ) ++ res;
else if( nob > noa && neb <= nea ) ++ res;
nob = neb, noa = nea;
}
while( !ah.empty() ){
pair<int, char> aa = ah.front();
int t = aa.first;
char fa = aa.second;
ah.pop();
int nea;
if( fa == 'L' ) nea = noa - t;
else nea = noa + t;
if( noa < nob && nea >= nob || noa > nob && nea <= nob ) ++ res;
noa = nea;
}
while( !bh.empty() ){
pair<int, char> bb = bh.front();
int t = bb.first;
char fb = bb.second;
bh.pop();
int neb;
if( fb == 'L' ) neb = nob - t;
else neb = nob + t;
if( nob < noa && neb >= noa || nob > noa && neb <= noa ) ++ res;
nob = neb;
}
cout << res;
return 0;
}