TopCoder 練習

TheCoffeeTimeDivOne(SRM 479 Div1 Easy)

■問題
コーヒーと紅茶を乗客に配るのにかかる時間を求める問題．

■解法
全ての乗客に対して調べ上げても44,777,777回のループですので時間的には余裕．
ある乗客にコーヒーor紅茶のどちらを配るか，を調べるには，binarySearchでは間に合わないので，boolean配列を作りました．意外にもメモリが足りました．

view plainprint?

1. public class TheCoffeeTimeDivOne{  
2.  public long find(int n, int[] tea){  
3.   int max=44777777;  
4.   boolean[] f=new boolean[max+1];  
5.   for(int t:tea){  
6.    f[t]=true;  
7.   }  
8.   int t=0,c=0;  
9.   long ret=(long)n*4;  
10.   for(int i=n;i>=1;i--){  
11.    if(f[i]){  
12.     // tea  
13.     if(t==0){  
14.      ret+=47+i*2;  
15.     }  
16.     t=(t+1)%7;  
17.    }else{  
18.     if(c==0){  
19.      ret+=47+i*2;  
20.     }  
21.     c=(c+1)%7;  
22.    }  
23.   }  
24.   return ret;  
25.  }  
26. }  

public class TheCoffeeTimeDivOne{
 public long find(int n, int[] tea){
  int max=44777777;
  boolean[] f=new boolean[max+1];
  for(int t:tea){
   f[t]=true;
  }
  int t=0,c=0;
  long ret=(long)n*4;
  for(int i=n;i>=1;i--){
   if(f[i]){
    // tea
    if(t==0){
     ret+=47+i*2;
    }
    t=(t+1)%7;
   }else{
    if(c==0){
     ret+=47+i*2;
    }
    c=(c+1)%7;
   }
  }
  return ret;
 }
}