algorithm vito family - andstudy/forge GitHub Wiki

  /* @BEGIN_OF_SOURCE_CODE */
  
  /* @JUDGE_ID: hoimann 10041 C "median of numbers" */
  
  /* $Id$ */
  
  #include <stdio.h>
  
  #define MAX_N 500
  
  void main(void)
  {
  	int a[MAX_N];
  	int num_cases, n;
  	int left, right, i, j, pivot, temp, sum_dist;
  
  	scanf("%d", &num_cases);
  	while (num_cases-- > 0) {
  		scanf("%d", &n);
  		for (i=0 ; i<n ; i++)
  			scanf("%d", &(a[i]));
  
  		left = 0;
  		right = n - 1;
  		do {
  			pivot = a[left];
  			i = left;
  			j = right;
  			while (i <= j) {
  				while (i <= right && a[i] <= pivot)
  					i++;
  				while (j > left && a[j] >= pivot)
  					j--;
  				if (i < j) {
  					temp = a[i];
  					a[i] = a[j];
  					a[j] = temp;
  				}
  			}
  			a[left] = a[j];
  			a[j] = pivot;
  			if (j < n/2)
  				left = j + 1;
  			else
  				right = j - 1;
  		} while (j != n/2);
  		sum_dist = 0;
  		for (i=0 ; i<j ; i++)
  			sum_dist += (pivot - a[i]);
  		for (i=j+1 ; i<n ; i++)
  			sum_dist += (a[i] - pivot);
  		printf("%d\n", sum_dist);
  	}
  }
  
  /* @END_OF_SOURCE_CODE */

  import java.io.*;
  import java.util.ArrayList;
  import java.util.Collections;
  
  
  class VitoMain {
  	
  	public static void main(String args[])
  	{
  		VitoMain vito = new VitoMain();
  		
  		vito.run();
  	}
  	
  	public void run()
  	{
  		int testCase = Integer.parseInt(readLine());
  		String printResult = "";
  		
  		if( testCase <= 0 || testCase >= 500)
  			return;
  		
  		while(testCase != 0)
  		{			
  			printResult += "" + sumDistance(readLine()) + "\n";
  
  			testCase--;
  		}
  		
  		System.out.println(printResult);
  	}
  
  	/* sort 후 중간지점을 vito point 로 */
  	public int sumDistance(String in) 
  	{
  		ArrayList<Integer> famList = new ArrayList<Integer>();
  		String[] data = in.split(" ");
  			
  		for(int i=1; i< data.length ; i++)
  		{
  			famList.add(Integer.parseInt(data[i]));
  		}
  		
  		Collections.sort(famList);
  		
  		
  		int result=0;
  		
  		for(int i=0; i< famList.size(); i++)
  		{
  			result += Math.abs(famList.get(Integer.parseInt(data[0])/2) - famList.get(i));
  		}
  		
  		return result;
  	}
  
  	public String readLine()
  	{
  		String data = null;
  		
  		try
  		{
  			BufferedReader is = new BufferedReader(new InputStreamReader(System.in));
  			data = is.readLine();
  		}
  		catch(IOException e)
  		{
  			System.out.println("IOException " +e);
  		}
  		
  		return data;		
  	}
  	
  }

  import junit.framework.TestCase;
  
  
  public class VitoMainTest extends TestCase {
  
  	VitoMain vito = new VitoMain();
  	
  	public void testAddVitoFam()
  	{
  		assertEquals("1",2,vito.sumDistance("2 2 4"));
  		assertEquals("1",4,vito.sumDistance("3 2 4 6"));
  		assertEquals("1",3,vito.sumDistance("2 5 2"));
  		assertEquals("1",5,vito.sumDistance("4 4 2 3 6"));
  		assertEquals("1",100,vito.sumDistance("5 2 3 4 5 100"));
  	}
  
  }

 /* @JUDGE_ID:parkpd 110401 Cpp "test" */
 
 /* @BEGIN_OF_SOURCE_CODE */
 
 #include <iostream>
 #include <vector>
 #include <set>
 #include <string>
 #include <strstream>
 #include <algorithm>
 #include <map>
 
 //#define _UNIT_TEST
 
 using namespace std;
 
 namespace ATUtil
 {
 
 bool IsInRange(int value, int from, int to)
 {
 	return (from <= value) && (value <= to);
 }
 
 int ConvertToIndex(char c)
 {
 	if ('a' <= c && c <= 'z')
 	{
 		return c - 'a';
 	}
 	else
 	{
 		return -1;
 	}
 }
 
 char ConvertToChar(int i)
 {
 	return (char)i + 'a';
 }
 
 typedef map<int, int> IntDB;
 typedef vector<int> Ints;
 
 };
 
 using namespace ATUtil;
 
 #ifdef _UNIT_TEST
 
 #include "../UnitTest++/src/UnitTest++.h"
 
 int main()
 {
 	UnitTest::RunAllTests();
 
 	char temp;
 	cin >> temp;
 
 	return 0;
 }
 
 #endif
 
 // code implement
 
 namespace ATCode
 {
 
 class CSolver
 {
 public:
 	unsigned int GetDistanceSumFromPos(int i);
 	unsigned int FindOptimalPos();
 	unsigned int _FindOptimalPos(int from, int to);
 
 	void Insert(int num);
 
 	template<typename InputIterator>
 	void Inserts(InputIterator beg, InputIterator end);
 
 	template<typename InputIterator>
 	static unsigned int GetSolution(InputIterator beg, InputIterator end);
 
 	IntDB m_FamilyStreetDB;
 };
 
 unsigned int CSolver::GetDistanceSumFromPos(int i)
 {
 	unsigned int sum = 0;
 	IntDB::iterator it = m_FamilyStreetDB.begin();
 	for (; it != m_FamilyStreetDB.end(); ++it)
 	{
 		int addr = it->first;
 		int nums = it->second;
 		sum += (abs(i - addr) * nums);
 	}
 
 	return sum;
 }
 
 unsigned int CSolver::FindOptimalPos()
 {
 	IntDB::iterator from = m_FamilyStreetDB.begin();
 	IntDB::reverse_iterator to = m_FamilyStreetDB.rbegin();
 
 	return _FindOptimalPos(from->first, to->first);
 }
 
 unsigned int CSolver::_FindOptimalPos(int from, int to)
 {	
 	int fromV = GetDistanceSumFromPos(from);
 	int toV = GetDistanceSumFromPos(to);
 	int mid = (to + from) / 2;
 
 	if (from == mid)		// 결정의 시간
 	{
 		return min(fromV, toV);
 	}
 
 	if (fromV < toV)
 	{
 		return _FindOptimalPos(from, mid);
 	}
 	else if (toV < fromV)
 	{
 		return _FindOptimalPos(mid, to);
 	}
 	else
 	{
 		return min(_FindOptimalPos(from, mid), _FindOptimalPos(mid, to));
 	}
 }
 
 void CSolver::Insert(int num)
 {
 	m_FamilyStreetDB[num]++;
 }
 
 template<typename InputIterator>
 void CSolver::Inserts(InputIterator beg, InputIterator end)
 {
 	for (InputIterator it = beg; it != end; ++it)
 	{
 		m_FamilyStreetDB[*it]++;
 	}
 }
 
 template<typename InputIterator>
 unsigned int CSolver::GetSolution(InputIterator beg, InputIterator end)
 {
 	CSolver s;
 	s.Inserts(beg, end);
 	return s.FindOptimalPos();
 }
 
 class CConsole
 {
 public:
 	static void ConsoleTest(istream& input, ostream& output);
 };
 
 void CConsole::ConsoleTest(istream& input, ostream& output)
 {
 	//ostrstream tempOutput;
 
 	int testCount = 0;
 	input >> testCount;
 
 	int relatives = 0;
 	int streetNumber = 0;
 
 	for (int i = 0; i < testCount; ++i)
 	{
 		input >> relatives;
 
 		CSolver s;
 
 		for (int j = 0; j < relatives; ++j)
 		{
 			input >> streetNumber;
 			s.Insert(streetNumber);
 		}
 
 		//tempOutput << s.FindOptimalPos() << std::endl;
 		output << s.FindOptimalPos() << std::endl;
 	}
 
 	//tempOutput << std::ends;
 
 	//output << tempOutput.str();
 };
 
 }
 
 using namespace ATCode;
 
 #ifndef _UNIT_TEST
 
 int main()
 {
 	CConsole::ConsoleTest(cin, cout);
 
 	return 0;
 }
 
 #else
 
 // tests
 
 TEST(FindOptimalPos)
 {
 	int inputs[] = {2};
 	CHECK_EQUAL(0, CSolver::GetSolution(&inputs[0], &inputs[1]));
 }
 
 TEST(FindOptimalPos1)
 {
 	int inputs[] = {2, 4, 6};
 	CHECK_EQUAL(4, CSolver::GetSolution(&inputs[0], &inputs[3]));
 }
 
 TEST(FindOptimalPos2)
 {
 	// 가족이 같은 주소에 둘 이상 사는 경우.
 	int inputs[] = {2, 2, 10};
 	CHECK_EQUAL(8, CSolver::GetSolution(&inputs[0], &inputs[3]));	// 위치는 2
 }
 
 TEST(FindOptimalPos3)
 {
 	int inputs[] = {2, 4};
 	CHECK_EQUAL(2, CSolver::GetSolution(&inputs[0], &inputs[2]));
 }
 
 TEST(FindOptimalPos4)
 {
 	int inputs[] = {5, 2};
 	CHECK_EQUAL(3, CSolver::GetSolution(&inputs[0], &inputs[2]));
 }
 
 TEST(FindOptimalPos5)
 {
 	int inputs[] = {4, 2, 3, 6};
 	CHECK_EQUAL(5, CSolver::GetSolution(&inputs[0], &inputs[4]));
 }
 
 TEST(FindOptimalPos6)
 {
 	int inputs[] = {2, 3, 4, 5, 100};
 	CHECK_EQUAL(100, CSolver::GetSolution(&inputs[0], &inputs[5]));
 }
 
 TEST_FIXTURE(CSolver, GetDistanceSumFromPos)
 {
 	int inputs[] = {2, 6, 8};
 	Inserts(&inputs[0], &inputs[3]);
 	CHECK_EQUAL(6, FindOptimalPos());
 
 	CHECK_EQUAL(10, GetDistanceSumFromPos(2));
 	CHECK_EQUAL(9, GetDistanceSumFromPos(3));
 	CHECK_EQUAL(8, GetDistanceSumFromPos(4));
 	CHECK_EQUAL(7, GetDistanceSumFromPos(5));
 	CHECK_EQUAL(6, GetDistanceSumFromPos(6));
 	CHECK_EQUAL(7, GetDistanceSumFromPos(7));
 	CHECK_EQUAL(8, GetDistanceSumFromPos(8));
 }
 
 TEST(ConsoleTest)
 {
 	stringstream input;
 	stringstream output;
 
 	input << "2\n2 2 4\n3 2 4 6\n";
 	CConsole::ConsoleTest(input, output);
 	CHECK_EQUAL("2\n4\n", output.str());
 }
 
 #endif
 
 /* @END_OF_SOURCE_CODE */

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.Scanner;
  import java.util.Set;
  class Main implements Runnable{
  	public int getVitoHousePos(int [] addrs){
  		int max=Integer.MIN_VALUE ;
  		int min=Integer.MAX_VALUE;
  		for(int curVal : addrs){
  			min = Math.min(min, curVal);
  			max = Math.max(max, curVal);
  		}
  		int midPos = min +  (max-min)/2;
  		return midPos;
  	}
  
  	public int getRelativeDistance(int[] datas,int housePos) {
  		Set<Integer> set = new HashSet<Integer>();
  		for(int curInt : datas){
  			set.add(curInt);
  		}
  		
  		int sum=0;
  		Iterator<Integer> i=set.iterator();
  		while(i.hasNext()){
  			int curInt = i.next();
  			sum += Math.abs(curInt - housePos);
  		}
  		return sum;
  	}
  	
  	public static void main(String[] args) throws Exception, IOException {
  		Main main = new Main();
  		main.run();
  	}
  
  	public void run() {
  		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  		int cases;
  		try {
  			cases = Integer.parseInt(reader.readLine().trim());
  		
  			for(int i=0;i<cases;i++){
  				Scanner scanner = new Scanner(System.in);
  				int itemSize = scanner.nextInt();
  				int [] datas = new int[itemSize];
  				for(int j=0;j<itemSize;j++){
  					datas[j] = scanner.nextInt();
  				}
  				
  				int housePos = getVitoHousePos(datas);
  				int result = getRelativeDistance(datas, housePos);
  				System.out.println(result);
  			}
  		} catch (NumberFormatException e) {
  			e.printStackTrace();
  		} catch (IOException e) {
  			e.printStackTrace();
  		}
  	}
  }

  import static org.junit.Assert.*;
  
  import org.junit.Test;
  
  
  public class MainTest extends Main{
  	private int [] test1 = {2,4};
  	private int [] test2 = {2,4,6};
  	private int [] test3 = {2,3,2};
  	@Test
  	public void testGetVitoHouse(){
  		Main main = new Main();
  		assertEquals(3, main.getVitoHousePos(test1));
  		assertEquals(4, main.getVitoHousePos(test2));
  		assertEquals(2, main.getVitoHousePos(test3));
  	}
  	
  	public void testGetRelativeDistance(){
  		Main main = new Main();
  		assertEquals(2, main.getRelativeDistance(test1,main.getVitoHousePos(test1)));
  		assertEquals(4, main.getRelativeDistance(test2,main.getVitoHousePos(test2)));
  		assertEquals(1, main.getRelativeDistance(test3,main.getVitoHousePos(test3)));
  	}
  }

  #include <vector>
  #include <algorithm>
  #define abs(x) ((x)>0?(x):-(x))
  using namespace std;
  
  int main()
  {
  	int TestCase;
  	
  	scanf("%d", &TestCase);
  
  	while( TestCase-- )
  	{
  		int family;
  		vector<int> arrayFamily;
  
  		scanf("%d", &family);
  
  		int temp;
  
  		for(int i = 0; i < family; i++ )
  		{
  			scanf("%d", &temp);
  			arrayFamily.push_back(temp);
  		}
  
  		sort(arrayFamily.begin(), arrayFamily.end());
  		temp = arrayFamily[arrayFamily.size()/2];
  
  		int result = 0;
  
  		for(int i = 0; i < arrayFamily.size(); i++ )
  		{
  			result += abs(temp - arrayFamily[i]);
  		}
  
  		printf("%d\n", result);
  
  		
  	}
  
  	return 0;
  }

  |1-m| + |3-m| + |5-m| + |7-m| + |9-m| = 최소값 

  < 추가 증명 시도 >
  위 식을 풀면,
      (m-1) + (m-3) + (7-m) + (9-m) = m에 상관없이 상수만으로 답이 나옴!!
  
     즉, median 을 중심으로 좌우의 개수가 같다면 m 은 다 지워지므로 최소값 상수C 되는 것이고, 
     좌우의 개수가 다르다면,  상수C - m 이 되서 최소값이 되는 것!