题解：P13132 [GCJ 2018 Qualification] Saving The Universe Again

kobebraint · 2025-07-10 09:26:48 · 题解

看题

要求通过最少次相邻交换，将总伤害降低到 \leq D。不能做到就输出 IMPOSSIBLE。

怎么做？

每个 s 的伤害由前面所有 c 的乘积决定，所以我们要尽量把 c 向后移，减小 c 的影响。
首先，不断从右往左找 cs，换成 sc，每次交换后计算一次总伤害；如果伤害 \leq D，结束；如果无法再换，输出 IMPOSSIBLE。

上代码

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

#define ll long long
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll T,d;
string p;

ll calc(string s){
    ll res=0,pw=1;
    for(auto c:s){
        if(c=='C') pw*=2;
        else res+=pw;
    }
    return res;
}

int main(){
    cin>>T;
    foru(t,1,T){
        cin>>d>>p;
        ll ans=0;
        while(1){
            if(calc(p)<=d) break;
            bool ok=0;
            for(ll i=p.size()-2;i>=0;i--){
                if(p[i]=='C'&&p[i+1]=='S'){
                    swap(p[i],p[i+1]);
                    ans++,ok=1;
                    break;
                }
            }
            if(!ok){
                ans=-1;
                break;
            }
        }
        cout<<"Case #"<<t<<": ";
        if(ans==-1) cout<<"IMPOSSIBLE"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}