争吵

OR124. 争吵

描述

有n 个人排成了一行队列，每个人都有一个站立的方向：面向左或面向右。由于这n 个人中每个人都很讨厌其他的人，所以当两个人面对面站立时，他们会发生争吵，然后其中一个人就会被踢出队列，谁被踢出队列都是有可能的。

我们用字符L 来表示一个面向左站立的人，用字符R 来表示一个面向右站立的人，那么这个队列可以用一个字符串描述。比如RLLR 就表示一个四个人的队列，其中第一个人和第二个人是面对面站立的。他们发生争吵后队列可能会变成LLR，也可能变成RLR；若变成RLR，则第一个人与第二个人还会发生争吵，队列会进一步变成LR 或者RR。

若在某个时刻同时可能有很多的争吵会发生时，接下来只会发生其中的一个，且任意一个都是有可能发生的。

你想知道经过一系列的争吵后，这个队列最少会剩下多少人？

输入描述

第一行包含一个有字符L 和R 构成的字符串。

1 ≤字符串长度≤ 10⁵

输出描述

输出队列中最少会剩下多少人。

示例1

输入:

LRRLRL

输出:

说明:

一种可能的变化情况是这样的:

LRRLRL -> LRLRL -> LRRL -> LRL -> LR

C 解法, 执行用时: 3ms, 内存消耗: 348KB, 提交时间: 2022-02-12

#include<stdio.h>
#include<string.h>
int main()
{
    char str[100001];
    scanf("%s",str);
    int len = strlen(str);
    int p1,p2;
    for(p1 = 0;p1 < len && str[p1] == 'L';p1++);
    for(p2 = len - 1;p2 >= 0 && str[p2] == 'R';p2--);
    p2 > p1 ? printf("%d",p1 + len - p2) : printf("%d",p1 + len - p2 -1);
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 424KB, 提交时间: 2022-02-11

#include <iostream>
#include <cassert>
using namespace std;
int repeat_code(string &str)
{
    int len = str.length();
    assert(len && len<=100000);
    for(char ch : str)
        assert(ch=='L' || ch=='R');
    int l = 0;
    while(l<len && str[l]=='L')
        ++l;
    if(l == len) return len;
    int r = len-1;
    while(r>l && str[r]=='R')
        --r;
    return l+len-r;
}
int main(void)
{
    string str;
    while(cin >> str)
        cout << repeat_code(str) << '\n';
    return 0;
}