백준17612 쇼핑몰

작성일 | In

문제 출처

  • 2019 KOI 1차 고등부 1번

사용 알고리즘

  • Segment Tree

시간복잡도

  • O(NlgN)

풀이

각각의 계산대를 세그먼트 트리의 리프 노드로 관리할 것 입니다.
고객들은 적게 대기를 하는 계산대, 대기 시간이 같다면 번호가 작은 계산대에 배정이 됩니다.
최솟값을 관리하는 세그먼트 트리의 노드를 아래와 같이 선언해줍시다.

1
2
3
4
5
6
7
struct SegNode{
	int w, idx;
	bool operator < (const SegNode &x) const {
		if(w != x.w) return w < x.w;
		return idx < x.idx;
	}
};

w는 대기 시간, idx는 계산대 번호입니다. 당연히 모든 리프 노드의 idx값은 고정입니다.

고객들의 정보를 저장하는 구조체인 User, 고객들이 나갈 때의 정보를 저장하는 구조체인 Mall을 만들어줍시다.

1
2
3
4
5
6
7
8
9
10
struct User{
	int id, w;
};
struct Mall{
	int time, idx, user; //나가는 시간, 이용한 게산대, 회원 번호
	bool operator < (const Mall &x){
		if(time != x.time) return time < x.time;
		return idx > x.idx;
	}
};

끝나는 시간이 빠를수록 먼저 나가고, 끝나는 시간이 같다면 번호가 더 큰 계산대를 이용한 고객이 먼저 나갑니다.
그러므로 위 코드처럼 less operator를 정의를 합니다.

고객들은 들어온 순서대로 처리를 해주면 됩니다. 자세한 구현은 아래 코드를 참고하시면 됩니다.

전체 코드

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct User{
	int id, w;
};

struct Mall{
	int time, idx, user;
	bool operator < (const Mall &x){
		if(time != x.time) return time < x.time;
		return idx > x.idx;
	}
};

struct SegNode{
	int w, idx;
	bool operator < (const SegNode &x) const {
		if(w != x.w) return w < x.w;
		return idx < x.idx;
	}
};

struct SegTree{
	SegNode tree[808080];
	int bias;
	void init(int n){ for(bias=1; bias<n; bias<<=1); }
	void update(int x, SegNode v){
		tree[x += bias] = v;
		while(x >>= 1){ tree[x] = min(tree[x << 1], tree[x << 1 | 1]); }
	}
	SegNode query(int l, int r){
		l += bias, r += bias; SegNode ret = {1000000007, 0};
		while(l < r){
			if(l & 1) ret = min(ret, tree[l++]);
			if(~r & 1) ret = min(ret, tree[r--]);
			l >>= 1, r >>= 1;
		}
		if(l == r) ret = min(ret, tree[r]);
		return ret;
	}
} seg;

vector<User> input;
vector<Mall> out;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k; cin >> n >> k; input.resize(n+1); seg.init(k);
	for(int i=1; i<=n; i++){
		cin >> input[i].id >> input[i].w;
	}
	for(int i=1; i<=k; i++) seg.update(i, {0, i});
	for(int i=1; i<=n; i++){
		auto segResult = seg.query(1, k);
		int w = segResult.w;
		int idx = segResult.idx;

		Mall now;
		now.time = w + input[i].w;
		now.idx = idx;
		now.user = input[i].id;
		seg.update(idx, {now.time, idx});
		out.push_back(now);
	}
	sort(out.begin(), out.end());
	ll ans = 0, cnt = 1;
	for(auto i : out) ans += (i.user * cnt++);
	cout << ans << "\n";
}