问一道FB面试题 - 未名空间(mitbbs.com)

问一道FB面试题 - 未名空间(mitbbs.com)
我们的手机，几乎每个键都对应字母： key2 -> 'abc', key3 -> 'def', key4 -> '
ghi'....老式的手机打字的原理是，如果你要打出a，你需要按1下key2. 如果要打出b
，你需要按2下key2， 打出c就要按3下key2，因为c排在key2的第三位。

所以题目是给出，keySize[] 每个element代表能存放的最多character， 比如上面的
例子就是[3,3,3],因为每个key都能最多放3个字母； 还有frequency[]，每个element
代表每个character出现的频率。要求把character排入key中，通过上面的方法打出所
有frequency数组中的character，最少的按键次数。

下面给个例子，比如我们的keysize是 [3,1,2]，我们的character的frequency是 [3，
3, 3， 2,1,1]。 如果把frequency中头三个字母index0 - index2放入key1， index3
放入key2，index4-index5放入key3，这样的按键次数就是 3*1 + 3*2 + 3*3 + 2*1 +
1*1 + 1*2。character可以打乱随意放，只要不超过keySize的limit。

follow up的要求就是character必须要找 frequency的order来，index2必能放在
index1之前。
Greedy:
http://likemyblogger.blogspot.com/2015/09/mj-36-arrange-keys.html

 int clicks(vector<int> keySize, vector<int> frequency){

        int n = frequency.size(), ret = 0, pos = 0, i = 0;

        sort(frequency.begin(), frequency.end(), greater<int>());

        while(i<n){

            for(int j=0; j<(int)keySize.size(); ++j){

                if(i==n) break;

                if(j==0) pos++;

                if(pos<=keySize[j]){

                    ret += frequency[i++]*pos;

                }

            }

        }

        return ret;

    }

};

int main(){

  vector<int> keySize = {3,1,2};

  vector<int> frequency = {2,1,1,3,3,3};

  Solution sol;

  cout<<sol.clicks(keySize, frequency)<<"?=18"<<endl;

  return 0;

}

Read full article from 问一道FB面试题 - 未名空间(mitbbs.com)