백준 8980번 택배 C++

출처 : https://www.acmicpc.net/problem/8980

 

1. 도착지점을 기준으로 오름차순 정렬을 한다. 도착지점이 같을 경우에는 시작지점을 기준으로 오름차순 정렬을 한다.

   (시작지점을 기준으로 정렬을 하면 독점이 일어날 수 있다.)

2. 각 지점마다 트럭의 용량을 저장하는 벡터를 만들고, 시작지점에서 도착지점까지 중 가장 트럭에 짐이 많이 실린 용량

   을 찾는다.

3. 트럭의 짐의 용량 + 내 용량이 c보다 크면 짐을 실을 수 있는 만큼만 자른다.

4. 시작지점부터 도착지점까지 내 짐의 무게가 트럭에 더해진다.

5. 2~4를 m만큼 반복한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, c, m;

struct box {
	box(int start, int end, int capacity) :start(start), end(end), capacity(capacity) {}
	int start;
	int end;
	int capacity;
};

bool compare(const box& lhs, const box& rhs) {
	if (lhs.end == rhs.end) {
		return lhs.start < rhs.start;
	}
	return lhs.end < rhs.end;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> c >> m;
	int ans = 0;
	vector<box> boxes;
	vector<int> truck(n + 1, 0);
	for (int i = 0; i < m; i++) {
		int start, end, capacity;
		cin >> start >> end >> capacity;
		boxes.push_back(box(start, end, capacity));
	}
	sort(boxes.begin(), boxes.end(), compare);

	for (int i = 0; i < m; i++) {
		int max_capacity = 0;
		//시작지점에서 도착지점까지 중 가장 트럭에 짐이 많이 실린 용량을 찾는다.
		for (int j = boxes[i].start; j < boxes[i].end; j++) {
			max_capacity = max(max_capacity, truck[j]);
		}
		// 트럭의 짐의 용량 + 내 용량이 c보다 크면 짐을 실을 수 있는 만큼만 자른다.
		int myCapacity = boxes[i].capacity;
		if (myCapacity + max_capacity > c) {
			myCapacity = c - max_capacity;
		}
		ans += myCapacity;
		//시작지점부터 도착지점까지 내 짐의 무게가 트럭에 더해진다.
		for (int j = boxes[i].start; j < boxes[i].end; j++) {
			truck[j] += myCapacity;
		}
	}
	cout << ans;
};