[Programmers] 택배 배달과 수거하기

https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

 

The key is to eliminate the farthest houses.

To identify the farthest ones, we may use max heaps.

 

1. Python

import heapq
def solution(cap, n, deliveries, pickups):
    h1 = []
    h2 = []
    for i, d in enumerate(deliveries):
        if d > 0:
            heapq.heappush(h1, (-i-1, d))
    for i, p in enumerate(pickups):
        if p > 0:
            heapq.heappush(h2, (-i-1, p))
    ret = 0
    while h1 or h2:
        if not h1:
            ret += 2 * -h2[0][0]
        elif not h2:
            ret += 2 * -h1[0][0]
        else:
            ret += 2 * max(-h1[0][0], -h2[0][0])
        c1 = cap
        while h1 and c1 > 0:
            i, d = heapq.heappop(h1)
            if d > c1:
                heapq.heappush(h1, (i, d - c1))
                c1 = 0
            elif d == c1:
                break
            else:
                c1 -= d
        c2 = cap
        while h2 and c2 > 0:
            i, d = heapq.heappop(h2)
            if d > c2:
                heapq.heappush(h2, (i, d - c2))
                c2 = 0
            elif d == c2:
                break
            else:
                c2 -= d
    return ret

 

2. C++

struct comparator {
	bool operator()(pair<int, int> p1, pair<int, int> p2) {
		return p1.first < p2.first;
	}
};


long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
	auto comp = [](pair<int, int> p1, pair<int, int> p2) {
		return p1.first < p2.first;
	};
	//priority_queue <pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq1;
	//priority_queue <pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq2;
	priority_queue <pair<int, int>, vector<pair<int, int>>, comparator> pq1;
	priority_queue <pair<int, int>, vector<pair<int, int>>, comparator> pq2;
	for (int i = 0; i < deliveries.size(); i++) {
		if (deliveries[i] > 0) {
			pq1.push({ i + 1, deliveries[i] });
		}
	}
	for (int i = 0; i < pickups.size(); i++) {
		if (pickups[i] > 0) {
			pq2.push({ i + 1, pickups[i] });
		}
	}
	long long ret = 0;
	while (!pq1.empty() or !pq2.empty()) {
		if (pq1.empty())
			ret += 2 * pq2.top().first;
		else if (pq2.empty())
			ret += 2 * pq1.top().first;
		else
			ret += 2 * max(pq1.top().first, pq2.top().first);
		int c1 = cap, c2 = cap;
		while (!pq1.empty() and c1 > 0) {
			auto[i, d] = pq1.top();
			pq1.pop();
			if (d > c1) {
				pq1.push({ i, d - c1 });
				c1 = 0;
			}
			else if (d == c1) {
				break;
			}
			else {
				c1 -= d;
			}
		}
		while (!pq2.empty() and c2 > 0) {
			auto [i, d] = pq2.top();
			pq2.pop();
			if (d > c2) {
				pq2.push({ i, d - c2 });
				c2 = 0;
			}
			else if (d == c2) {
				break;
			}
			else {
				c2 -= d;
			}
		}
	}
	return ret;
}