Codeforces Global Round 11 B. Chess Cheater (贪心,结构体排序)

题意:你和朋友进行了\(n\)个回合的棋艺切磋,没有平局,每次要么输要么赢,每次赢可以得一分,假如前一局也赢了,那么可以得两分,结果已成定局,但是你确可以作弊,最多修改\(k\)个回合的结果,问你作弊后最多可以得多少分.
题解:假如有\(WLW\),我们让中间的\(L\)变成\(W\),那么就能得到\(5\)分,贪心,然后发现,优先让两个\(W\)中间的\(L\)变为\(W\)是最优的,我们可以求所有两个\(W\)之间\(L\)的数量并且记录位置,然后按数量排序,先让含\(L\)数量小的变成\(W\),全部改完后\(k\)可能还会有剩余,再优先将\(W\)的相邻的\(L\)变成\(W\),如果还有剩余,就将\(L\)变为\(W\),此时我们修改得到的字符串一定是最优的,计算答案即可.

代码:

struct misaka{

    int pos;

    int val;

    bool operator < (const misaka & mikoto) const{

        return val<mikoto.val;

    }

}e;

int t;

int n,k;

string s;

vector<misaka> v;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    while(t--){

        cin>>n>>k;

        cin>>s;

        v.clear();

        int len=(int)s.size();

        int l=0,r=0;

        while(l<len && s[l]=='L') l++;

        r=l;

        while(r<len){

            while(r<len && s[r]=='W') r++;

            if(r>=len) break;

            l=r-1;

            while(r<len && s[r]=='L') r++;

            if(r>=len) break;

            e.pos=l+1;

            e.val=r-l-1;

            v.pb(e);

        }

        sort(v.begin(),v.end());

        for(auto o : v){

            int p=o.pos;

            while(s[p]=='L' && k){

                k--;

                s[p]='W';

                p++;

            }

        }

        for(int i=0;i<len;++i){

            if(s[i]=='W' && k){

                if(s[i+1]=='L') {s[i+1]='W';k--;}

            }

        }

        for(int i=len-1;i>=0;--i){

            if(s[i]=='W' && k){

                if(s[i-1]=='L') {s[i-1]='W';k--;}

            }

        }

        for(int i=0;i<len;++i){

            if(s[i]=='L' && k){

                s[i]='W';

                k--;

            }

        }

        int ans=0;

        for(int i=0;i<len;++i){

            if(s[i]=='W'){

                if(s[i-1]=='W') ans+=2;

                else ans++;

            }

        }

        cout<<ans<<'\n';

    }

    return 0;

}

巴特西

Codeforces Global Round 11 B. Chess Cheater (贪心,结构体排序)

最新文章

热门文章