SRM572 Div2 Medium(500) NextOrPrev

NextOrPrev

ae→{0,1}, acb→{0,2,1}のように、各文字の文字列中での順位を表す配列を考える。startとgoalでの配列が一致していれば変換可能、一致していなければ途中で同じ文字になってしまうので不可能。変換可能なら貪欲に変換すれば良い。

#include <string>
#include <vector>
using namespace std;

//  各文字の文字列中での辞書順を返す
vector<int> Rank( string w )
{
    int n = (int)w.size();
    vector<int> R(n);
    for ( int i=0; i<n; i++ )
        for ( int j=0; j<n; j++ )
            if ( w[j]<w[i] )
                R[i]++;
    return R;
}

class NextOrPrev{public:
int getMinimum( int nextCost, int prevCost, string start, string goal )
{
    if ( Rank(start)!=Rank(goal) )
        return -1;

    int ans = 0;
    for ( int i=0; i<(int)start.size(); i++ )
    {
        if ( start[i]<goal[i] )
            ans += nextCost*(goal[i]-start[i]);
        if ( start[i]>goal[i] )
            ans += prevCost*(start[i]-goal[i]);
    }

    return ans;
}};