백준8980 택배

작성일 | In

문제 링크

  • http://icpc.me/8980

문제 출처

  • 2013 전국 본선 초등2

사용 알고리즘

  • 그리디

시간복잡도

  • O(m log m)

풀이

트럭은 한번 방문한 도시를 다시 방문하지 않고 1번 도시부터 출발하기 때문에 1번 도시와 가까운 순으로 박스를 옮겨서 최적의 해를 구할 수 있습니다.

먼저 박스 데이터를 입력 받아서 도착지 순으로, 같다면 출발지 순으로 정렬을 합니다.
gogo[i]에 i번째 마을에서 트럭에 있는 택배의 개수가 저장을 하겠습니다.
left라는 변수는 트럭에 더 담을 수 있는 양을, maxi라는 변수는 현재 택배를 처리하는 도중 가장 많이 적재된 양을 나타냅니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

struct asdf{
	int s, e, x;
	bool operator < (asdf a){
		if(e != a.e) return e<a.e;
		return s<a.s;
	}
};

int n, c, m;
vector<asdf> v;

int main(){
	cin>>n>>c>>m;
	v.resize(m);
	for(int i=0; i<m; i++) cin >> v[i].s >> v[i].e >> v[i].x;
	sort(v.begin(), v.end());

	int ans = 0;
	vector<int> gogo(n+1);
	for(int i=0; i<m; i++){
		int maxi = 0;
		for(int j=v[i].s; j<v[i].e; j++) maxi = max(maxi, gogo[j]);
		int left = min(v[i].x, c-maxi);
		ans += left;
		for(int j=v[i].s; j<v[i].e; j++) gogo[j] += left;
	}
	cout << ans;
}