D - Face Produces Unhappiness

D - Face Produces Unhappiness

atcoder-ABC140

题意:

  1. 如果字符串中有s[i-1]=s[i],happy的人数+1
  2. 我们能进行的操作是,选定一个区间将字符整体反转(LR
  3. 最多进行k次操作(注意不是一定进行K次操作)

思路:

  1. 我们先记录原始字符串中happy的人数(只要s[i-1]==s[i],即LL类型或者RR类型,因为我们每次只讨论相邻两个的性质)
  2. 那么剩余在字符串中,只剩LR类型和RL类型
    eg:LRLRL或者RLRL(至少是三个字符及以上是这种LRL或RLR类型),我们会发现无论是翻转L或者R,都可以获得三个连续相等的字符,使得happy人数+2
  3. 所以我们新增加的happy人数就是2*k,但是!一个字符串中最多的happy人数是n-1个人,所给出的k为最多进行的操作,可能远远大于我们实际能进行的最多操作!
    所以需要取happy=min(happy+2*k,n-1);
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	int happy=0;
	for(int i=1;i<n;i++)
	if(s[i]==s[i-1]) happy++;
	cout<<min(happy+2*k,n-1)<<endl;
	
	return 0;
}
上一篇:Navicate “happy” 使用的实现:


下一篇:屏幕小宠物(python3.8.5版)