题目:
有 N 个人从东向西排成一排,每个人的状态用一个字符串 S 表示,第i个字符
表示从西边数起第 ii 个人的朝向L 表示面朝西, R 表示面朝东。
对于队伍中的每个人,如果自己面前的人的朝向和自己一样,那么这个人就会感到幸福。如果面前的人朝向和自己不一样,或者面前没有人,这个人就感到不幸福。
你可以进行以下操作最多 K 次(也可以一次都不进行):
选择整数,让从西边数起第
个人转身180度。
经过最多 次操作后,感到幸福的人最多有多少人?
思路:贪心,每次翻转最多只能增加两个人,那么k次之后最多只能增加到n-1个人
#include<cstdio> using namespace std; char str[100005]; int n,k,x[100005],ans; int main() { scanf("%d %d %s",&n,&k,str+1); for(int i=1;i<=n;i++) x[i]=(str[i]=='L'); for(int i=0;i<=n;i++) x[i]^=x[i+1]; for(int i=1;i<n;i++) ans+=(x[i]==0); ans+=2*k; if(ans>=n) ans=n-1; printf("%d",ans); }