P9012 [USACO23JAN] Moo Operations B 题解

LegendaryGrandmaster · 2023-02-04 17:23:48 · 题解

铜组全部题解

首先字符串至少要有 3 位，没有直接输出 -1。

我们三位三位模拟取最小值，只要中间是 O，都可以变成 MOO。

操作次数如下：

1. MOO：0 次。
2. MOM：1 次。
3. OOO：1 次。
4. OOM：2 次。

最终取最小值加上总长度 -3 即可。因为最终只能保留 3 位。如果 mi 仍是初始值，那么输出 -1。

#include<bits/stdc++.h>
using namespace std;

signed main()
{
    int t;
    cin>>t;
    while(t--){
        int mi=0x3f3f3f3f;
        string st;
        cin>>st;
        if(st.size()<3){
            puts("-1");
            continue;
        }
        for(int i=0;i<st.size()-2;i++){
            string str=st.substr(i,3);
            if(str=="MOO")mi=min(mi,0);
            else if(str=="MOM")mi=min(mi,1);
            else if(str=="OOO")mi=min(mi,1);
            else if(str=="OOM")mi=min(mi,2);
        }
        if(mi==0x3f3f3f3f)puts("-1");
        else cout<<mi+st.size()-3<<'\n';
    }
}