题解：B4193 [2023 海淀区小学组] 排座位

dg114514 · 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;
}