java programming

Question

Some people remain old fashioned and John is one of them. He doesn't like the new smart phones with full keypads and still uses the old keypads which require you to tap a key multiple times to type a single letter. For example, if the keyboard has two keys, one with the letters "adef" and the other one with the letters "zyx", then typing 'a' requires one keystroke, typing 'f' requires four keystrokes, typing 'y' requires two keystrokes, and so on.

He recently moved to a new country where the language is such that his keypad is not the most efficient. In every language some characters occur more often than others. He wants to create a specific keyboard for this language that uses N different letters. He has a large body of text in this language, and has already analyzed it to find the frequencies of all N letters of its alphabet.

You are given an array 'frequencies' with N elements. Each element of frequencies is the number of times one of the letters in the new language appears in the text John has. Each element of frequencies will be strictly positive. (I.e., each of the N letters occurs at least once.)

You are also given an array keySize. The number of elements of keySize is the number of keys on the keyboard. Each element of keySize gives the maximal number of letters that maybe put on one of the keys.

Find an assignment of letters to keys that minimizes the number of keystrokes needed to type the entire text. Output that minimum number of keystrokes. If there is not enough room on the keys and some letters of the alphabet won't fit, Output -1 instead.

Input Format

1. The first line will contain a number 'N' that specifies the size of 'frequencies' array
2. The second line will contain N numbers that form the frequencies array
3. The third line contains a number 'K' that specifies the size of the 'keySize' array
4. The fourth line contains K numbers that form the keySize array

Output Format

1. Output a single integer that is answer to the problem.

Constraints

1. frequencies will contain between 1 and 50 elements, inclusive.
2. Each element of frequencies will be between 1 and 1,000, inclusive.
3. keySizes will contain between 1 and 50 elements, inclusive.
4. Each element of keySizes will be between 1 and 50, inclusive.

SAMPLE INPUT

 

4

7 3 4 1

2

2 2

SAMPLE OUTPUT

 

19

Explanation

The foreign language has four letters. Let us call them W, X, Y and Z. John's text contains seven Ws, three Xs, four Ys, and one Z. The keyboard has two keys, each of them may contain at most two letters. One optimal solution is to use the keys "WZ" and "YX". We can then type each W and each Y using a single keystroke, and we need two keystrokes for each X and each Z. Therefore, the total number of keystrokes when typing the entire text will be 71 + 32 + 41 + 12 = 19.

Answer 1

I would sort the frequency table from most frequent to least frequent.

Each frequency record is inserted in the proper location (using insertion sort)

one at a time.

Then assign the keys, distributing them evenly. beginning with

the most frequent.

So in your example, the sorted array: 7W, 4Y, 3X, 1Z

then key1 gets W

key 2 gets Y

key 1 gets X

key 2 gets Z

this is exactly the solution you have posted....

(source code pending,..... give me some time)