백준17420 깊콘이 넘쳐흘러

작성일 | In

문제 링크

  • http://icpc.me/17420

문제 출처

  • 2019 선린 정올 2번

사용 알고리즘

  • 그리디

시간복잡도

  • O(NlgN)

풀이

(B[i], A[i])를 오름차순으로 정렬을 해준 다음에 최소 연장 횟수를 구해주면 됩니다.

A[i] < B[i]인 경우에는 A[i] >= B[i]가 되도록 미리 연장을 해줘야 합니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

vector<p> v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; v.resize(n);
	for(auto &i : v) cin >> i.x;
	for(auto &i : v) cin >> i.y;

	ll ans = 0;
	for(auto &i : v){
		if(i.x < i.y){
			ll t = (i.y - i.x + 30 - 1) / 30;
			i.x += t * 30;
			ans += t;
		}
	}

	sort(all(v), [&](p &a, p &b){
		if(a.y != b.y) return a.y < b.y;
		return a.x < b.x;
	});

	ll now = 0;
	for(int i=0; i<n; i++){
		int nxt = i + 1;
		while(nxt < v.size() && v[nxt-1].y == v[nxt].y) nxt++;

		for(int j=i; j<nxt; j++){
			if(v[j].x < now){
				int b = (now - v[j].x + 30 - 1) / 30;
				ans += b;
				v[j].x += 30 * b;
			}
		}

		sort(v.begin()+i, v.begin()+nxt, [&](p &a, p &b){
			if(a.y != b.y) return a.y < b.y;
			return a.x < b.x;
		});

		now = max(now, v[nxt-1].x);
		i = nxt - 1;
	}

	cout << ans;
}