SRM560 Div1 Easy(250), Div2 Medium(500) TomekPhone

TopCoder

TomekPhone

出現数の多い文字から順に、キーストロークの少ない位置に割り振っていく。

#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

class TomekPhone{public:
int minKeystrokes( vector <int> occurences, vector <int> keySizes )
{
    sort(occurences.begin(),occurences.end(),greater<int>());

    vector<int> K;
    for ( int i=0; i<(int)keySizes.size(); i++ )
        for ( int j=1; j<=keySizes[i]; j++ )
            K.push_back(j);
    sort(K.begin(),K.end());

    if ( occurences.size() > K.size() )
        return -1;

    int ans = 0;
    for ( int i=0; i<(int)occurences.size(); i++ )
        ans += K[i]*occurences[i];
    return ans;
}};