백준3090 차이를 최소로

작성일 | In

문제 링크

  • http://icpc.me/3090

문제 출처

  • 2012 Junior Croatian Olympiad in Informatics - Additional task 1번

사용 알고리즘

  • Parametric Search

시간복잡도

  • O(N log(109))

풀이

차이를 최소로 만들어야 하는 문제입니다.
인접한 수의 차이는 최대 약 10억까지 가능합니다. 때문에, Parametric Search를 요구하는 문제라는 것을 알 수 있습니다.

T번의 계산만으로 N개의 수에서 인접한 수들의 차이를 모두 mid 이하로 줄일 수 있을 지의 여부를 이용하여 탐색을 O(log (109))만에 수행을 해주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;
typedef pair<int, p> pp;

long long n, t;
vector<int> v;

bool chk(int mid){
	long long cnt = 0;
	vector<int> arr;
	for(auto i : v) arr.push_back(i);

	for(int i=1; i<n; i++){
		if(arr[i-1]+mid < arr[i]){
			cnt += arr[i] - (arr[i-1] + mid);
			arr[i] = arr[i-1] + mid;
		}
		if(cnt > t) return false;
	}

	for(int i=n-1; i>0; i--){
		if(arr[i]+mid < arr[i-1]){
			cnt += arr[i-1] - (arr[i] + mid);
			arr[i-1] = arr[i] + mid;
		}
		if(cnt > t) return false;
	}
	return true;
}

void print(int mid){
	vector<int> arr;
	for(auto i : v) arr.push_back(i);

	for(int i=1; i<n; i++){
		if(arr[i-1]+mid < arr[i]){
			arr[i] = arr[i-1] + mid;
		}
	}

	for(int i=n-1; i>0; i--){
		if(arr[i]+mid < arr[i-1]){
			arr[i-1] = arr[i] + mid;
		}
	}

	for(auto i : arr) cout << i << " ";
}

int main(){
	cin >> n >> t;
	v.resize(n);
	int l = 0, r = 0;
	for(int i=0; i<n; i++) cin >> v[i], r = max(r, v[i]);
	int mid;
	for(int i=0; i<500; i++){
		mid = (l+r) >> 1;
		if(chk(mid)) r = mid;
		else l = mid;
	}
	print(r);
}