Programming Challenges – 여행 (The Trip)

문제 <- 클릭

하면 할수록 채점 로봇이 몹시 까다롭다는것을 느낀다.

퀵정렬.. 이론상으로는 알고 있지만 직접 구현하니까 역시 효율적으로 하는것이 만만치 않다. 결국 위키 백과에 있는것을 참고 했다. 사실 제공 되는 함수를 쓰면 되지만 그래도 공부니까..

#include 
#include 
#define MAX_STUDENT 1000
using namespace std;

void qSort(int* arr, int left, int right) { //기본 제공 되지만... 공부를 위해
    int pivot = arr[left];
    int left_hold, right_hold;
    left_hold = left;
    right_hold = right;
    while (left < right) {
        while ((arr[right] >= pivot) && (left < right))
            right--;
        if (left != right) {
            arr[left] = arr[right];
            left++;
        }
        while ((arr[left] <= pivot) && (left < right))
            left++;
        if (left != right) {
            arr[right] = arr[left];
            right--;
        }
    }
    arr[left] = pivot;
    pivot = left;
    left = left_hold;
    right = right_hold;
    if (left < pivot)
        qSort(arr, left, pivot - 1);
    if (right > pivot)
        qSort(arr, pivot + 1, right);
}
void quickSort(int* arr, int arr_size) {
    qSort(arr, 0, arr_size - 1);
}
int main() {
    int students[MAX_STUDENT];
    int average, sum = 0, result = 0;
    int numberOf1CentMore;
    int numberOfStudent;
    double temp;
    while (scanf("%d", &numberOfStudent) == 1) {
        if (!numberOfStudent)
            break;
        for (int i = 0; i < numberOfStudent; ++i) {
            scanf("%lf", &temp);
            students[i] = (int) (temp * 100 + 0.5); //integer로 변환 하면서 0.5를 더해 올림!!
            sum += students[i];
        }

        quickSort(students, numberOfStudent); //지불한 액수 순으로 정렬

        average = sum / numberOfStudent; //평균을 구하고
        numberOf1CentMore = sum % numberOfStudent; //나머지는 많이 낸사람들에게 분배

        for (int i = 0; i < numberOfStudent - numberOf1CentMore; ++i) {
            result += abs(students[i] - average); //차액의 절대값 누적
        }
        for (int i = numberOfStudent - numberOf1CentMore; i < numberOfStudent; ++i) {
            result += abs(students[i] - (average + 1)); //나머지를 1씩 더한 차액을 누적
        }

        result /= 2;

        printf("$%.2fn", result / 100.0);

        sum = 0;
        result = 0;
    }
    return 0;
}