Atcoder [Sep.7th] D题 Face Produces Unhappiness

Atcoder [Sep.7th] D题 Face Produces Unhappiness

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

问题大意:有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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注