题解归档 - cf2232C2

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2232C2
• 本地来源：problems/cf2232C2/idea.md
• 题目链接：https://codeforces.com/contest/2232/problem/C2
• 原始标题：CF2232C2 - Seating Arrangement (Hard)

思路

CF2232C2 - Seating Arrangement (Hard)

pattern:
one-parameter optimization / unimodal search

claim:
It is enough to decide how many A people are used as introverts. In an optimal
choice, if exactly m ambiverts open empty tables, they can be taken as the
first m A characters in the line.

why:
Opening a table earlier never hurts future E/A-as-E people, and it uses the
same one seat. Delaying an A-as-I can only make fewer non-empty seats
available before that point.

simulation:
For fixed m, scan the line:

• I or the first m A: if open < x, open a table and seat them.
• E or later A: if seated < open * s, seat them at a non-full opened table.

The value over m is discrete unimodal. C1 can enumerate all m; C2 binary
searches the first peak by comparing eval(m) and eval(m+1).

check:
For small cases, brute.cpp uses DP over (opened tables, seated people).

代码

来源：problems/cf2232C2/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,s;
ll eval(const string &u,ll m){
    ll open=0,seated=0;
    for(char c:u){
        if(c=='A'){
            if(m>0){
                m--;
                c='I';
            }else c='E';
        }
        if(c=='I'){
            if(open<x){
                open++;
                seated++;
            }
        }else{
            if(seated<open*s) seated++;
        }
    }
    return seated;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        ll n;
        string u;
        cin>>n>>x>>s>>u;
        ll cntA=0;
        for(char c:u) if(c=='A') cntA++;
        ll l=0,r=cntA;
        while(l<r){
            ll m=(l+r)/2;
            if(eval(u,m)<eval(u,m+1)) l=m+1;
            else r=m;
        }
        cout<<eval(u,l)<<"\n";
    }
    return 0;
}