自动搬运

查看原文

来自洛谷，原作者为

	dg114514 qq 8268838 欢迎加 || 壶关条件 U540059

搬运于2025-08-24 21:17:44，当前版本为作者最后更新于2025-03-03 20:44:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

有点类似插板？
首先，可以发现男生数量与女生数量互换结果不变。所以我们直接令男生数量一定不少于女生数量。（如果男生数量少，直接变性交换数量）
然后我们统计空座位的连通块。
一排座位，相邻不能相同的情况下，能分成这样：（0 为男生，1 为女生）010101010...。易得 0 有 $\lceil \frac{n}{2}\rceil$ 个，1 有 $\lfloor \frac{n}{2}\rfloor$ 个。显然，0 的数量一定不比 1 少。而根据贪心，可以知道多的人数耗的数量尽量要多。然后分别让男女数量减去对应的座位数量即可。

#include <bits/stdc++.h>
using namespace std;
int block[100005],top=0;
int main(){
	char c;
	int n,a,b,ans=0,cnt=0;
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>c;
		if(c=='*')block[++top]=cnt,cnt=0;//连通块
		else cnt++;						 //统计
	}
	if(cnt) block[++top]=cnt;
	for(int i=1;i<=top;i++){
		if(!a&&!b)break;//优化
		int t1=(block[i]+1)/2,t2=block[i]/2;//ceil(n/2) 和 floor(n/2)
		if(a<b)swap(a,b);//保证 a >= b
		t1=min(a,t1),t2=min(b,t2);
		a-=t1,b-=t2;
		ans+=t1+t2;
	}
	cout<<ans;
	return 0;
}