[Google Code Jam] Round 1A A번 - Minimum Scalar Product

문제 : http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiE2QUM

v1 = (x1,x2,x3....xn), v2 = (y1,y2,y3...yn)
이렇게 두 개의 벡터가 주어졌을 때 scalar product 값은
x1*y1 + x2*y2 + x3*y3 + ... + xn*yn 이다.

Minimum Scalar Product는 v1과 v2의 각 요소를 재배치하여
scalar product 값을 최소화 시키는 문제이다.

예를 들어 v1=(1 3 -5)  v2=(-2 4 1) 일 때
그냥 scalar product = 1*-2 + 3*4 + -5*1 = 5 이고
Minimum Scalar Product = -5*4 + 3*-2 + 1*1 = -25 이다.

이 문제는 주어진 인풋에 대해 각 벡터의 Minimum Scalar Product 값을 구하면 된다.

대충 알고리즘은 이렇다.

1. v1의 각 요소들을 오름차순으로 정렬한다
2. v2의 각 요소들을 내림차순으로 정렬한다.
3. Scalar Product를 수행한다.

저렇게 했을 때 최소값이 나온다. 나는 증명 못한다. 증명은 구글에게 물어볼 것.

대충 소스코드는 다음과 같다.(전체 소스코드는 생략함)

void Algorithm()     {         std::string line;         ReadLineFromFile(line);         int nCases = atoi(line.c_str());         for(int i=0; i<nCases; i++) // nCases=Minimum Scalar Product 문제 개수         {             /* n=v1,v2 벡터에 몇 개의 요소들이 있는가 */             do{                 ReadLineFromFile(line);             }while(line == "");             int n = atoi(line.c_str());             int* v1 = new int[n];             int* v2 = new int[n];                         /* v1 저장 */             for(int j=0; j<n; j++)                 ReadIntToken(v1[j]);             /* v2 저장 */             for(int j=0; j<n; j++)                 ReadIntToken(v2[j]);             /* 오름차순 정렬 (작은값이먼저) */             qsort(v1, n, sizeof(int), MinimumScalarProduct::AscOrder);             /* 내림차순 정렬 (큰값이먼저) */             qsort(v2, n, sizeof(int), MinimumScalarProduct::DescOrder);             long long sum = 0;             /* 각 벡터 요소의 곱이 integer의 범위를 넘기도 한다 */             for(int j=0; j<n; j++)                 sum += (long long)v1[j]*(long long)v2[j];                         /* 출력 형태 맞추기 */             char out[50];             /* %I64d로 출력해야 long long(__int64 출력된다) */             sprintf_s(out, 50, "Case #%d: %I64d", i+1, sum);             WriteLineToFile(out);             delete[] v1;             delete[] v2;                     }     }     static int __cdecl AscOrder(const void* a, const void* b)     { return (*(int*)a) - (*(int*)b); }     static int __cdecl DescOrder(const void* a, const void* b)     { return (*(int*)b) - (*(int*)a); }

하이라이팅 쉽게 하는 법 없을까;

SyntaxHighLighter 는 색이 맘에 안 들고;
vs2005에서 작성된 코드를 복사해서 마소 워드에 붙여넣어 다시 복사하여 블로그에 붙여넣으면 되긴 하는데
html 코드가 매~~~~~~~우 더러워진다. 워드용 xml 까지 덕지덕지 ㄷㄷㄷ