[백준] 3090번 차이를 최소로 (c++, 이분탐색)

하루 종일 디버깅 못해 쩔쩔맸지만 양질의 문제다 

차이를 mid로 둬서 이분탐색하는 건 알았지만 업데이트를 O(n^2)이 아닌 방법을 못 떠올렸다

 

100점이 안나오길래 다름 사람 코드 붙여넣어봤는데도 100이 안나와서 그냥 부분 성공했다

 

현재 위치 i를 업데이트 하면 이전 위치도 변경이 되는데 for문안에서 이중 포문 돌리는 것이 아니라

다시 반대 방향으로 for문을 돌리며 다시 업데이트 하면 된다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#define MAX_N 100001
#define MAX_K 1000000001
int n, k;
int arr[MAX_N];
int carr[MAX_N];
int ans[MAX_N];

int main(int argc, char** argv)
{

	//freopen("sample_input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);

		cin >> n >> k;
		int max_diff = 0;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			if (i + 1 < n) {
				max_diff = max(max_diff, arr[i] - arr[i + 1]);
			}
		}

		int left = 0, right = max_diff;//최소, 최대 차이값
		
		while (left <= right) {
			for (int i = 0; i < n; i++) {//원본 배열 복사
				carr[i] = arr[i];
			}
			int mid = (left + right) / 2;//차이의 최대값
			int cnt = 0;// 뺸 개수

			bool pass = true;
			for (int i = 0; i + 1 < n; i++) {
				int diff = carr[i + 1] - carr[i];
				if (diff>mid) {
					cnt += (diff - mid);//최소 차이 만큼은 빼준다
					carr[i + 1] -= (diff - mid);
				}
				
			}
			for (int i = n - 1; i >= 1; i--) {
				int diff = carr[i-1] - carr[i];
				if (diff > mid) {
					carr[i-1] -= (mid - diff);
					cnt += (mid - diff);
				}
			}

			if (cnt>k) {//최대값 통과 못함
				left = mid + 1;

			}
			else {
	
				for (int i = 0; i < n; i++) {
					ans[i] = carr[i];
				}
				right = mid - 1;

			}

		}

		for (int i = 0; i < n; i++) {
			cout << ans[i] << " ";
		}
	


	return 0;
}