Codeforces Round 966 (Div. 3)
D. Right Left Wrong
题意
思路
我们可以先预处理前缀和,然后贪心每次找最左边的L
和最右边的R
,计算区间和,然后缩小区间重复操作即可
时间复杂度
O(N)
void solve()
{
int n;
cin >> n;
vector<int> arr(n + 1);
vector<int> sum(n + 1);
fer(i, 1, n + 1)
{
cin >> arr[i];
sum[i] = sum[i - 1] + arr[i];
}
string s;
cin >> s;
s = " " + s;
int ans = 0;
int i = 1, j = n;
while (i < j)
{
while (i < j && s[i] != 'L')
i++;
while (i < j && s[j] != 'R')
j--;
if (i < j)
ans += sum[j] - sum[i - 1];
i++, j--;
}
cout << ans << '\n';
}