TopCoder 練習 OptimalQueues(SRM 297 Div1 Easy)

OptimalQueues(SRM 297 Div1 Easy)

■問題
一度の手続きにserviceTime分かかる窓口がtellerCount個ある．
既に入り口でclientArrivals[i]分待っている客がn人いる．全ての客に対して手続きを行うが，待ち時間の最大値を最小化したい．最小化するように客を選んだ時，その最小値はいくらか．

■解法
まずソートする．つまり，待ち時間clientArrivals[i]が大きい客から手続きを行う(この方法が最も待ち時間が少なくなるやり方)．この時，i番目の客の総待ち時間は，
clientArrivals[i]+(i/tellerCount+1)serviceTime
となる．i=[1,n]について調べ，最大値を返せば良い．

view plainprint?

1. import java.lang.*;  
2. import java.util.*;  
3.   
4. public class OptimalQueues{  
5.  public int minWaitingTime(int[] clientArrivals, int tellerCount, int serviceTime){  
6.   for(int i=0;i<clientArrivals.length;i++) clientArrivals[i]*=-1;  
7.   Arrays.sort(clientArrivals);  
8.   for(int i=0;i<clientArrivals.length;i++) clientArrivals[i]*=-1;  
9.   int ret=0;  
10.   for(int i=0;i<clientArrivals.length;i++){  
11.    ret=Math.max(ret,clientArrivals[i]+(i/tellerCount+1)*serviceTime);  
12.   }  
13.   return ret;  
14.  }  
15. }  

import java.lang.*;
import java.util.*;

public class OptimalQueues{
 public int minWaitingTime(int[] clientArrivals, int tellerCount, int serviceTime){
  for(int i=0;i<clientArrivals.length;i++) clientArrivals[i]*=-1;
  Arrays.sort(clientArrivals);
  for(int i=0;i<clientArrivals.length;i++) clientArrivals[i]*=-1;
  int ret=0;
  for(int i=0;i<clientArrivals.length;i++){
   ret=Math.max(ret,clientArrivals[i]+(i/tellerCount+1)*serviceTime);
  }
  return ret;
 }
}