POJ 3273 Monthly Expense

解法

月の出費の上限で二分探索

ソースコード

int n, m;
int money[ten(5) + 100];
bool ok(int month_spend)
{
    int months = 1, spend = 0;
    rep(i, n)
    {
	if (spend + money[i] > month_spend)
	{
	    ++months;
	    spend = 0;
	}
	spend += money[i];
    }
    return months <= m;
}
int main()
{
    scanf("%d%d", &n, &m);
    rep(i, n)
	scanf("%d", money + i);

    int low = *max_element(money, money + n) - 1;
    int high = ten(9) + 100;
    while (high - low > 1)
    {
	int mid = (high + low) / 2;
	if (ok(mid))
	    high = mid;
	else
	    low = mid;
    }
    printf("%d\n", high);
}