Monday, January 26, 2015

Topcoder SRM 647 div2 500problem

I solve this problem in two way

one way is two for 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static int getMaxProfit(int M, int[] profit, int[] city, int[] visit){
  
  int len = visit.length;
  
  int sum = 0;
  int maxPossible=0;
  int maxCitiIndex=0;
  
  for (int i = 0; i < len; i++) {
   // find visitable array.
   
   boolean find = false;
   
   for(int j=0; j<city.length; j++){
    if(visit[i] == city[j]){
     if(maxPossible < profit[j]){
      maxPossible = profit[j];
      maxCitiIndex =j;
      find = true;
     }
    }
   }
   
   if(find){
    profit[maxCitiIndex] = 0;
    sum+= maxPossible;
   }
   
   maxPossible=0;
   maxCitiIndex=0;
  }
  
  return sum;
 }



and  the other is
make List array and reversOrder


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int getMaxProfit(int M, int[] profit, int[] city, int[] visit){
  ArrayList<Integer>[] list = new ArrayList[M+1];
  
  int max = 0;
  for (int i = 0; i < list.length; i++) {
   list[i] = new ArrayList<Integer>();
  }
  
  for (int i = 0; i < city.length; i++) {
   list[city[i]].add(profit[i]);
  }
  for (int i = 0; i < list.length; i++) {
   Collections.sort(list[i], Collections.reverseOrder());
  }
  
  for (int i = 0; i < visit.length; i++) {
   if(list[visit[i]].size() > 0){
    Integer x = list[visit[i]].remove(0);
    max += x; 
   }
  }
  return max;
 }

No comments:

Post a Comment