Tuesday, January 13, 2015

Topcoder SRM645 div2 500 Editorial ~!!

The problem site is : problem link

below is thinking of the steps of the problem.





and My code is here

If you have any question comment plz~



 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package srm645;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class ConnectingCarsMycode {
 
 private long minimizeCost(int[] position, int[] lengths) {
  int len = position.length;
  
  ArrayList<Car> cars = new ArrayList<Car>(len);
  for(int i=0; i<len; i++){
   Car car= new Car(position[i], lengths[i]);
   cars.add(car);
  }
  Collections.sort(cars,  new CustomComparator());
  
  int centerPosition = position.length/2;
  long totalMove = 0l;
  
  // left car to right 
  for(int i=centerPosition; i>0; i-- ){
   Car right= cars.get(i);
   Car left = cars.get(i-1);
   int move   = right.position - (left.position + left.length);
   left.position = left.position + move;
   totalMove += move;
  }
  
  // right car to left 
  for(int i=centerPosition; i<len-1; i++){
   Car left= cars.get(i);
   Car right = cars.get(i+1);
   int move   = right.position - (left.position + left.length);
   right.position = right.position -move; 
   totalMove += move;
  }
  
  return totalMove;
 }
 
 public class CustomComparator implements Comparator<Car>{
  @Override
  public int compare(Car o1, Car o2) {
   return o1.position - o2.position;
  }
 }
 
 public class Car {
  int position  ;
  int length;
  Car (int position, int length){
   this.position = position;
   this.length = length;
  }
  @Override
  public String toString() {
   return "Car [position=" + position + ", length=" + length + "]";
  }
 }
 
 public static void main(String args[]){
  int [] position = null;
  int [] lengths = null;
  position = new int[] {1, 3, 10, 20};
  lengths = new int[] {2, 2, 5, 3};
  
  ConnectingCarsMycode car = new ConnectingCarsMycode();
  
  System.out.println(car.minimizeCost(position, lengths));
  
  position = new int[] {100, 50, 1};
  lengths = new int[] {10, 2, 1};
  System.out.println(car.minimizeCost(position, lengths));
  
  position = new int[] {4, 10, 100, 13, 80};
  lengths = new int[] {5, 3, 42, 40, 9};
  System.out.println(car.minimizeCost(position, lengths));
  
  position = new int[] {5606451, 63581020, 81615191, 190991272, 352848147, 413795385, 468408016, 615921162, 760622952, 791438427};
  lengths = new int[] {42643329, 9909484, 58137134, 99547272, 39849232, 15146704, 144630245, 604149, 15591965, 107856540};
  System.out.println(car.minimizeCost(position, lengths));
 }
}

No comments:

Post a Comment