这类题见过好多次，刚总是不能很快做出来，要不然就是有几个测试点超出时限。

问题大意：有N人排成一队，队伍中的人不是面向左就是面向右，用长为N的字符串表示，字符串中仅含L与R，L表示这个人面向左，R表示这个人面向右。如果一个人面前的这个人和自己是同向的，那么他会感到happy。你在队伍外可以指挥这一队人，每次选取连续的小队，你可以将这些人旋转180度。比如让三个人LRR反转就是LLR。现给出这个队伍以及你可以指挥的次数，试问最后可以让愉快的人最大值是多少?

分析

建个模型，在下图中人的方向用箭头表示。图中，连续的同向的人我们用1个箭头表示。同时为了省去对边界的特别处理，再假设待计算的N人左侧有无数个面向右的人，而右侧有无数个面向左的人。

此题目标是计算愉快的人，但我们反其道而行之，计算那些不愉快的有几人（相邻两人面对面的情况）。也就是说，我们的优化目标是上图中红点更少。每个红点上都有两个不愉快的人。当然，若这个红点位于最左边或最右边，则就只有一个不愉快的人（因为在队伍外边的人不进行计算）。

当选择区间（l，r）并反转它时，这些红点和蓝点如何变化呢？

不在反转区间两顶点上的红点和蓝点并不会增减，并且仍保持原来的红蓝色。因此，一次操作就选择一个红点和一个蓝点分别作为选择区间的两端，这样可以删去一个红点。除此之外的选择方法不能把红点消去。 由我们假设左侧有无数个朝右的人，右侧有无数个朝左的人，因此红色或蓝色虚线的总数总是奇数，会按照[红、蓝、红、蓝、…、红]的排列出现。由此可以看出，若有M个红点，就有M-1个蓝点；因此，无论操作执行多少次，总会留下一个红点。这样的话，就可以先通过M-1次操作擦除M-1个红点。因此，尽可能地消去内部（不在队伍端点的）红点（这样每次可以增加2个快乐的人），如果最后剩下的红点在队内，则从红点到队伍端点全反转，则可以增加1个快乐的人。这是因为，一次操作中，愉快的人只能增加2个，而实际上对所全队来说每两个人都可能是待增加的。即，最后问题就转化为愉快人数+2可执行X次，使愉快人数+1可执行Y次，在K次操作中增加了多少愉快的人数。其中，X和Y由红点的数量确定，即，在S中出现的’RL’的数量，可由S1和SN确定。该解决方案的时间复杂度为O（N）。

另一种解法。把字符串分解为LL … L，RR … R，…，LL … L，其中有奇数段RR … R，通过从前面依次按顺序反转来计算最后的愉快人数，这同样是O（N）的时间复杂度。

#include<bits/stdc++.h>
#include <iostream>
using namespace std;
int main(void){
    int N,K; cin >> N >> K;
    string S;
    cin >> S;
    int score = 0;
    for(int i = 0; i < N-1; i++){
        if(S[i] == S[i+1]) score++;
    }
    int ans = min(score+2*K, N-1);
    cout << ans << "\n";
  	return 0;
}