1026번 보물

vector로 하고 싶었지만, C언어 공부할 겸 퀵 정렬을 이용해보았다.

A는 오름차순으로, B는 내림차순으로 하여

곱하면 그 값이 최솟값이 된다.

https://www.acmicpc.net/problem/1026

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int N = 0;
 
int A[101] = { 0, };
int B[101] = { 0, };
 
int partitionA(int start, int end)
{
    int pivot = end;
    int left = start;
    int right = end;
 
    while (left < right)
    {
        while (A[left] <= A[pivot] && left < right)
        {
            ++left;
        }
 
        while (A[right] >= A[pivot] && left < right)
        {
            --right;
        }
 
        if (left < right)
        {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
        }
    }
 
    int temp = A[right];
    A[right] = A[pivot];
    A[pivot] = temp;
 
    return right;
}
 
void quickSortA(int start, int end)
{
    int pivot = 0;
 
    if (start < end)
    {
        pivot = partitionA(start, end);
        quickSortA(start, pivot - 1);
        quickSortA(pivot + 1, end);
    }
}
 
int partitionB(int start, int end)
{
    int pivot = end;
    int left = start;
    int right = end;
 
    while (left < right)
    {
        while (B[left] >= B[pivot] && left < right)
        {
            ++left;
        }
 
        while (B[right] <= B[pivot] && left < right)
        {
            --right;
        }
 
        if (left < right)
        {
            int temp = B[left];
            B[left] = B[right];
            B[right] = temp;
        }
    }
 
    int temp = B[right];
    B[right] = B[pivot];
    B[pivot] = temp;
 
    return right;
}
 
void quickSortB(int start, int end)
{
    int pivot = 0;
 
    if (start < end)
    {
        pivot = partitionB(start, end);
        quickSortB(start, pivot - 1);
        quickSortB(pivot + 1, end);
    }
}
 
int main(void)
{
    int S = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &A[i]);
    }
 
    quickSortA(0, N - 1); // A는 오름차순
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &B[i]);
    }
 
    quickSortB(0, N - 1); // B는 내림차순
 
    for (int i = 0; i < N; i++)
    {
        S += (A[i] * B[i]);
    }
 
    printf("%d\n", S);
 
    return 0;
}