Eko solution

eko.cpp

// Eko <http://nztrain.com/problems/56>

#include <cstdio>
#include <climits>
using namespace std;

long long total_wood(int *trees, size_t n_trees, int sawblade) {
    long long total = 0;
    for (size_t i = 0; i != n_trees; ++i) {
        if (trees[i] > sawblade) {
            // Chop the tree! Yay!
            total += trees[i] - sawblade;
            }
        }
    return total;
    }

int main() {
    freopen("eko.in", "r", stdin);
    freopen("eko.out", "w", stdout);

    size_t n_trees;
    int target;
    scanf("%zu %d", &n_trees, &target);

    // Read in tree heights
    int trees[n_trees];
    for (size_t i = 0; i != n_trees; ++i) {
        scanf("%d", &trees[i]);
        }

    // Binary search the thing
    int lo = 0, hi = INT_MAX;
    while (lo <= hi) {
        // Find midpoint
        int mid = lo + ((hi - lo) / 2);
        long long cursor = total_wood(trees, n_trees, mid);
        // Since the function is monotonically *decreasing*, we need to
        // reverse the comparisons
        if (target >= cursor) {
            // Move left
            hi = mid - 1;
            }
        else {
            // Move right
            lo = mid + 1;
            }
        }

    // The algorithm is off by one sometimes
    if (total_wood(trees, n_trees, lo) < target) {
        --lo;
        }

    printf("%d\n", lo);

    return 0;
    }