COFO::1623C Balanced Stone Heaps

• Link : COFO::1623C

Problem

• level : 1600
• tag : binary search, greedy
• TIME
  • to understand :
  • to algorithm : fail
  • to code :
  • to debug :
  • understanding edit : 15
• 앞에서부터 iterating하는 걸로 풀려고 시도했지만 계속 TC 에서 하나씩 틀렸습니다가 나왔습니다.
• edit은 명쾌한 풀이를 제공합니다.

Point

• n개의 원소를 가진 array a가 주어집니다.
• a[i]는 i번째 heap에 있는 돌의 갯수를 의미합니다.
• 다음과 같은 순서의 작업이 이루어질때, 가장 작은 돌을 가지는 heap에 포함된 돌의 최대 갯수를 출력하시오.
  • 3번째 스톤부터 n번째 스톤까지 다음 작업이 이루어집니다.
  • 0 <= 3 * d <= h[i]인 d를 선택합니다.
  • (i-1)번째에 d개의 스톤을 더해주고, (i-2)번째애 2d 개의 스톤을 더해주고, i번째에서는 3d개의 스톤을 제외해줍니다.

Design

• 앞에서부터 풀려고 계속 했습니다.
• 하지만, d를 선택할때 애매한 부분이 생깁니다.
  • i에서 i-1과 i-2에 d를 나눠줄때
  • i-2만 만족시키고 넘겨야할지, i-2, i-1모두 만족시켜야할지, i번째엔 몇개의 스톤을 남겨야할지 등 말이죠.
  • 이러다보니, 예외처리로 코드만 덕지덕지해지기 쉽습니다.
• edit 은 명쾌하게 뒤에서부터의 풀이를 제시합니다.
• 필요한것만 남기고 앞으로 최대한 분배해주는 이 풀이에는 얼핏생각해도 예외가 없습니다.
• 단, 하나 주의할 점은 원래 순서는 앞에서 뒤로 가야하지만 이것을 거꾸로 하는 것이기 때문에
• 현재 스톤이 최초에 주어진 스톤보다 많아서는 안됩니다.
  • 뒤에서부터오면 이 경우가 생기기 때문이죠.
• 즉,
  • 최초에 주어진 돌을 3으로 나눠서 분배하거나
  • 현재 주어진 돌에서 목표갯수를 뺀 것에서 3으로 나눠서 분배하거나
  • 둘 중 작은 값을 택합니다.

Complexity

• O(nlog(max(h)))

Code

#include<bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define sz(a) (int) a.size()
#define rep(i, a, b) for(int i=(a); i <(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
typedef long long ll;
using namespace std;
const int MAXN = 2 * 1e5 + 9;

int n;
ll b[MAXN];
ll a[MAXN]; // copied
bool possible(ll mid) {
    rep(i, 0, n) a[i] = b[i];

    r_rep(i, n-1, 1) {
        if(a[i] < mid) return false;
        ll d = min(b[i], a[i] - mid) / 3;
        a[i] -= d * 3, a[i-1] += d, a[i-2] += d * 2;
    }
    return a[0] >= mid && a[1] >= mid;
}
void bs(ll st, ll en) {
    ll ans = -1;
    while(st <= en) {
        ll mid = (st + en) >> 1;
        if (possible(mid)) {
            ans = max(ans, mid);
            st = mid + 1;
        } else en = mid - 1;
    }
    cout << ans << '\n';
}
void solve() {
    cin >> n;
    rep(i, 0, n) cin >> b[i];
    ll h = *max_element(b, b + n);
    
    bs(1, h);
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}