当前位置: 首页 > 工具软件 > bed > 使用案例 >

Omkar and Bed Wars

何和惬
2023-12-01

题意:n个人站成一圈,一个人如果只被一个人攻击,那么他只能回击攻击者,如果被两个人同时攻击,那么可以攻击任意一个,现在给你一个L,R组成的字符串,L表示向左边攻击,R表示向右边攻击,现在问你需要改变多少个人的朝向才能使得所有的人都可以满足上述要求。

如果所有人的初始方向不一样。对于一串全部都是R的字符串,两侧都是L。
当R的个数为1和2时不用改变初始方向。
当R的个数为3LRRRL时,我们需要改变一个,成为LRRLL。
当R的个数为4时,需要改变一次,成为LRRLRL。
当R个数为5时,需要改变一次,成为LRRLRRL。
当R的个数为6时,需要改变两次,成为LRRLRRLL

我们可以发现每三个R需要将第三个R变为L就可以使得这一小段满足条件,当一串全部都是L时同理可的。

如果所有人的初始方向一样。
如果长度为3时,如LLL,只需要改变一次,变成LLR。
当长度为4时,如LLLL,对于前三个,我们改变一次后可以得到LLRL,由于这是一个圈,所以LLRL相当于LLLR,还需要一次操作,变成LLRR,总次数为两次,这是我们也可以发现我们的目标是避免出现连续三个同方向的人。
当长度为5时,如LLLLL,第一次操作后:LLRLL,第二次操作后LLRLR,此时已符合条件。
当长度为6时,我们需要两次操作使得字符串变成LLRLLR。
当长度为7时,两次操作后仍然存在LLL,所以需要三次操作。。。。

规律:当所有人的初始方向一致时,ans+=len/3+(len%3==0)?0:1,当所有人的初始方向不是都相同时,ans+=len/3.

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		int n,ans=0,sign=0,cnt=0;
		string str;
		cin >> n >> str;
		str = str + str;
		//cout << str;
		for (int i = 0; i < n; i++) {//判断是否朝向都相同
			if (str[i] != str[0]) {
				sign = i;
				break;
			}
		}
		if (!sign) {
			if (n < 3) ans = 0;
			else ans = (n / 3) + ((n % 3 == 0) ? 0 : 1);
			cout << ans << endl;
			continue;
		}
		int rem = sign;
		for (int i = sign; i < sign + n; i++) {
			if (str[i] == str[rem]) cnt++;
			else {
				ans += cnt / 3;
				cnt = 1;
				rem = i;
			}
		}
		ans += cnt / 3;
		cout << ans << endl;
	}
}
 类似资料:

相关阅读

相关文章

相关问答