Codeforces Round #763 (Div. 2) - C. Balanced Stone Heaps

문제 링크 : Problem - C - Codeforces

Problem - C - Codeforces

 

이진탐색  + 그리디 문제이다.

옮길 수 있는 최소 돌 x에 대하여 해당 돌이 문제에서 주어진 작업에 해당하면서 n 부터 3 까지 돌을 이동시키면서 마지막에 놓여진 1, 2 번째 돌의 갯수가 x 이상일 경우를 살피는 문제이다.

이러한 최소 돌 x를 바이너리 서칭을 함으로써 최대로 얻을 수 있는 x를 찾고 해당 답이 정답이 된다.

 

핵심이 되는 부분 : check 하는 과정에서 돌을 옮길 수 d 에 대하여 d = min(h[i], cur_h[i] - x) / 3 를 잡는 점이다.

돌을 옮기는 수(d)를 구하는 과정에서 이동할 수 있는 돌의 수(cur_h[i] - x)가 기존에 있던 돌의 수(h[i])보다 초과해서는 안된다.

 

Solution Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int n;
int h[200001];

bool check(int x) {
	vector<int> cur_h(h, h + n);
	for (int i = n - 1; i >= 2; i--) {
		if (cur_h[i] < x) return false;
		int d = min(h[i], cur_h[i] - x) / 3;
		cur_h[i - 1] += d;
		cur_h[i - 2] += 2 * d;
	}
	return cur_h[0] >= x && cur_h[1] >= x;
}

void test() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> h[i];
	int l = 0, r = *max_element(h, h + n);
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout << (l + r) / 2 << endl;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--) test();

	return 0;
}