自动搬运

查看原文

来自洛谷，原作者为

	FL_sleake 漫漫月华无边

搬运于2025-08-24 23:04:02，当前版本为作者最后更新于2024-07-06 13:21:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Fun fact

样例三所给出的 $n$ 场对局来源于 FL_sleake 和 SnowTrace 单挑的真实数据。并且 FL_sleake 一共给了 SnowTrace 七个盖帽。

解题思路

由于只需要考虑后续比赛，所以给出来的 $n$ 场比赛可以直接处理掉。具体地，设 $s$ 中有 $tx$ 个 F，有 $ty$ 个 S，我们把 $x$ 设置为 $x-tx$，把 $y$ 设置为 $y-ty$。

为了让小 F 获胜，小 S 最多获胜 $y-1$ 场。那么问题转化成了有 $x$ 个球，你需要放 $y-1$ 个挡板，问最多的连续的球数最少是多少。由于 $y-1$ 个挡板可以产生 $y$ 个空位，所以把球尽量均匀地放进去就可以了，答案为 $x$ 除以 $y$ 上取整的结果。

单个数据复杂度为 $\Theta(n)$。

代码示例

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,x,y,n;
string s;
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>x>>y;
		int sumx=0,sumy=0;
		cin>>s;
		s=" "+s;
		for(int i=1;i<=n;i++){
			if(s[i]=='F') sumx++;
			else sumy++;
		}
		x-=sumx;
		y-=sumy;
		cout<<(x+y-1)/y<<endl;
	}
	return 0;
}