POJ 3273 Monthly Expense 题解 《挑战程序设计竞赛》

POJ 3273 Monthly Expense

分期：将N个账款分割成M个财务期，使得每个分期账款和的最大值最小。

3.1不光是查找值！“二分搜索”

最大化最小值

无非是判断条件的选择而已，我选取C(d) := 是否需要M以上个分期，才使得每个分期的花费不大于d。如果条件为真的话，说明mid取得太小，二分搜索的下限太小了，那就把下限调大一点。否则根本不需要M个分期，说明mid太大，把上限调小一点。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
#define MAX_N 100000 + 16
int N, M;
ULL money[MAX_N];

bool C(ULL d)
{
	int periods  = 1;
	ULL expenses = 0;
	for (int i = 0; i < N; ++i)
	{
		expenses += money[i];
		if (expenses > d)
		{
			expenses = money[i];
			++periods;
		}
	}
	if (periods > M)
	{
		return true;
	}
	return false;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		cin >> money[i];
	}
	ULL lb = *max_element(money, money + N), ub = accumulate(money, money + N, 0);
	while (lb < ub)
	{
		ULL mid = (lb + ub) / 2;
		if (C(mid))
		{
			lb = mid + 1;
		}
		else
		{
			ub = mid;
		}
	}
	cout << lb << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3273 Monthly Expense 题解 《挑战程序设计竞赛》