(UVA) Vito's Family - Solution 1

I used Brute Force to solve this problem.


import java.io.*;
import java.util.*;

class Main {
    public static void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        int numCases = Integer.parseInt(br.readLine());
        for (int i = 0; i < numCases; i++) {
            String line = br.readLine();
            String[] s = line.split("\\s");
            int numRelatives = Integer.parseInt(s[0]);
          
            int[] streetHouses = new int[numRelatives];
            for (int j = 0; j < numRelatives; j++) {
                streetHouses[j] = Integer.parseInt(s[j+1]);
            }         
          
            Arrays.sort(streetHouses);
          
            int sum = 0;
            for (int j = 0; j < numRelatives; j++) {
                sum += Math.abs(streetHouses[0]-streetHouses[j]);
            }
           
            int streetsOnLeft = 1;
            int streetsOnRight = numRelatives-1;
            int minDistance = 2000000000;
            for (int j = 1; j < numRelatives; j++) {
                int currStreet = streetHouses[j];
                int previousStreet = streetHouses[j-1];
                sum = sum + (streetsOnLeft-streetsOnRight)*(currStreet-previousStreet);
               
                if (sum < minDistance) {
                    minDistance = sum;
                }
               
                streetsOnLeft++;
                streetsOnRight--;
            }
                                
            bw.write(minDistance + "\n");
        }
      
        bw.flush();
        bw.close();
                              
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução