Monthly Expense (POJ 3273)

We use binary search to guess a monthly expense value and verify if it is feasible with gready strategy. As every expense in each day must be arranged to one of the months, we can start from the first day and put as many as days into this month as possible as long as the total expense won't exceed our guessed value. If at last we can divide the days into less than or equal to M months, then the value is feasible.

If the value is feasible, we should try decrease the value as to find the minimum one, or we increase the value.

import java.io.*;
import java.util.*;

public class MonthlyExpense {
    private static boolean canDivide(int[] expense, int v, int M) {
        long sum = 0;
        for (int e : expense) {
            if (sum + e > v) {
                if (e > v) return false;
                if ((--M) <= 0) return false;
                sum = e;
            } else {
                sum += e;
            }
        }
        return true;
    }
    private static void solve(int[] expense, int M) {
        int l = 0, u = 1000000000;
        while (l <= u) {
            int mid = (l + u) / 2;
            if (canDivide(expense, mid, M)) u = mid - 1;
            else l = mid + 1;
        }
        System.out.println(l);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(), M = in.nextInt();
        int[] expense = new int[N];
        for (int i = 0; i < N; i++) {
            expense[i] = in.nextInt();
        }
        solve(expense, M);
    }
}