CSES 2. Stick Lengths (1074)

출처: https://cses.fi/problemset/task/1074

---

문제 설명

There are n sticks with some lengths. Your task is to modify the sticks so that each stick has the same length.

You can either lengthen and shorten each stick. Both operations cost x where x is the difference between the new and original length.

What is the minimum total cost?

입력  

The first input line contains an integer n: the number of sticks.

Then there are n integers: p_1,p_2,…,p_n: the lengths of the sticks.

출력  

Print one integer: the minimum total cost.

입력 예

5
2 3 1 5 2

출력 예

5

제약조건

• 1 <= n <= 2x10^5
• 1 <= p_i <= 10^9

---

문제 풀이 내용

입력받은 막대 길이를 정렬하고, median 값을 기준으로 비용을 계산한다.

프로그램 내용

...
    for (int idx = 0; idx < nStick; idx++)
        cin >> num_array[idx];

    sort(num_array, num_array+nStick);

    long target = num_array[nStick/2];
    long long sum = 0;

    for(int idx=0; idx < nStick; ++idx)
        sum += abs(target - num_array[idx]);
...

 

Sorting and Searching ( link )