BOJ 25045 비즈마켓

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

문제

비즈마켓은 “고객 기업 운영의 효율화에 기여하며, 그 구성원의 복지 만세를 추구한다.” 라는 기조 아래 기업을 주 대상으로 복지몰 사업, 기업 판촉 및 사은품 사업, 산업재 유통 사업을 하는 온라인 종합상사입니다. 이 주 사업 분야 외에도 비즈마켓은 브랜드 사업, 렌탈 사업, 에너지 사업 등 다양한 분야에서 사업을 진행하고 있습니다. 오늘 신욱이는 비즈마켓으로부터 효율적으로 렌탈 사업을 운영하는 것을 도와달라는 의뢰를 받았습니다.

비즈마켓에는 $N$개의 물품이 있고, 물품을 렌탈하기를 원하는 $M$개의 고객 기업이 있습니다. 각 물품은 $A_i$ 의 만족도를 가지고 있으며, 각 고객 기업은 $B_j$ 의 비용을 지불하여 렌탈을 진행하고자 합니다. 각 고객 기업은 하나의 물품만 렌탈할 수 있으며, 각 물품 또한 하나의 고객 기업에만 렌탈해줄 수 있습니다.

$A_i$ 의 만족도를 가지는 물품을 $B_j$ 의 비용을 지불하고자 하는 고객 기업에 렌탈해주게 되면 $A_i - B_j$ 만큼의 고객 만족도를 얻을 수 있습니다. 모든 고객 기업들은 적어도 자신이 지불한 비용만큼의 만족도를 얻기를 원하기 때문에, 고객 만족도가 $0$보다 작아진다면 거래를 진행하지 않을 것입니다. 거래를 진행하지 않으면 당연히 고객 만족도도 얻을 수 없습니다.

신욱이가 구체적으로 해야 하는 일은 각 고객 기업에 렌탈해 줄 물품을 잘 정해서 고객 만족도의 합을 최대로 만드는 것입니다. 하지만 신욱이는 해야 할 과제가 너무 많았던 나머지, 이 일을 여러분들한테 넘기고 과제를 하러 떠나버렸습니다. 신욱이를 대신해 고객 만족도의 합의 최댓값을 구해줍시다.

---

입력

첫 번째 줄에는 상품의 수를 의미하는 정수 $N$과 고객 기업의 수를 의미하는 정수 $M$이 공백으로 구분되어 주어집니다. $( 1 \le N, M \le 2 \times 10^5 )$ 

두 번째 줄에는 각 상품의 만족도 $A_1, A_2, A_3, \dots, A_N$ 을 의미하는 정수 $N$개가 공백으로 구분되어 주어집니다. $(0 \le A_i \le 10^9)$ 

세 번째 줄에는 고객 기업이 지불하고자 하는 비용 $B_1, B_2, B_3, \dots, B_M$ 을 의미하는 정수 $M$개가 공백으로 구분되어 주어집니다. $(0 \le B_j \le 10^9)$ 

---

출력

첫 번째 줄에 각 고객 기업에 대여해 줄 물품을 잘 골라서 얻을 수 있는 고객 만족도의 합의 최댓값을 출력합니다.

---

예제 입력 1

5 5
6 7 8 9 10
2 3 4 5 6

예제 출력 1

20

예제 입력 2

5 3
927291536 144432154 222251432 846751354 648975123
105423157 28465 1354216

예제 출력 2

2316212175

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> products = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> customers = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            products.offer(Integer.parseInt(st.nextToken()));
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            customers.offer(Integer.parseInt(st.nextToken()));
        }

        long answer = 0;
        int searchBoundary = Integer.min(N, M);

        for (int i = 0; i < searchBoundary; i++) {
            int satisfaction = products.poll() - customers.poll();

            if(satisfaction >= 0) {
                answer += satisfaction;
            }
        }

        System.out.println(answer);
    }
}