Java - Text Messaging Problem

這是我在一個面試時所寫到的題目，大家可以自行至網路上搜尋到，如下：

https://open.kattis.com/problems/textmessaging

文章的內容我就不提了(因為我英文不好orz)，紀錄一下自己解題方法!

有趣的是，文章提到的訊息點擊字母的例子，其實可以拿非智慧型手機來看看就可以聯想的

到了(小弟手上還在用XD)，以1 ~ 9按鍵來說，如1可以登打a ~ c的字母，但是您若要登打abc

，需要點擊1+2+3 = 6(次)，比起智慧型手機來說真的是不太方便(汗)

在這邊它有提到一些input and output的規則，如下：

#Input說明

第一行數字為N => 表示此次有幾個case

接下來的行數以奇數行三個數字表示P、K、L各有不同定義

P => 一個按鍵最多有幾個字母可以選擇

K => 表示當下有幾個按鍵可以使用

L => 表示當下的case有幾個字母輸出

而接著偶數行承襲上一行的奇數行，表示輸出的字母使用頻率

以sample而言，

2
3 2 6
8 2 5 2 4 9
3 9 26
1 1 1 100 100 1 1 1 1 1 1 1 1 1 1 1 1 10 11 11 11 11 1 1 1 100

2 => N

3 2 6 

8 2 5 2 4 9 => case 1

#Output說明

表示輸出各個case最小點擊次數 => 當下字母最小點擊次數 * 使用頻率

處理方法

1. 讀檔(.txt)，檢查case個數是否與下面的資料吻合

2. 檢查每個case之P * K >= L

3. 實際計算部分

將每個case的字母輸出頻率該行資料，split後儲存至陣列內，再由大到小進行排序(陣列F)

程式碼片段如下：

   //Limits
   if(P * K >= L){
      int click = 1; //最小點擊次數
      int j = 0; //控制click變化的變數
      //走訪每個字母,在計算當下所有點擊次數 = 頻率 * 最小點擊次數
      for(int ii = 0 ; ii < presses.length ; ii++){
         if(K == j){
            click++; //增加最小點擊次數
            j = 1; //reset
         }else{
            j++;
         }
         //System.out.println(click+","+F[ii]);
         min_press_total += click * Integer.parseInt(F[ii]);
      }
      String output = "Case #%s: "+min_press_total;
      System.out.println(String.format(output, i));
   }else{
      String output = "Case #%s: P * K must >= L";
      System.out.println(String.format(output, i));
      break;
   }

走訪每個字母被使用的頻率，並且以每個按鍵點擊第一次 * 頻率最大的為原則，依序遞增

點擊次數、遞減頻率以此取得每個case的最小點擊次數。以sample來解說，排序完如下

9 8 5 4 2 2，以程式來看的話計算如下：

9 * 1 + 8 * 1 + 5 * 2 + 4 * 2 + 2 * 3 + 2 * 3 = 47(次)

當計算使用頻率8次的字母時，會以另一個按鍵點擊一次可以取得為原則，字母頻率使用越

小的會以點擊次數最多的為主!

PS. 大致作法如上，若有更完美的作法請不吝指教，謝謝