Monthly Expense（最大化最小值问题）

最新推荐文章于 2018-07-24 16:21:54 发布

free-dancer

最新推荐文章于 2018-07-24 16:21:54 发布

阅读量1.2k

点赞数

分类专栏：二分

本文链接：https://blog.csdn.net/Joined/article/details/77102742

版权

农夫约翰面临财务困扰，需为未来的每一天安排预算，并定义连续的"fajomonths"来最小化最高支出。问题转化为在已知每天花费的情况下，如何分组以使最大花费最小。通过二分法寻找最大化的最小值，确保每月支出限制得以实现。样例解释了如何通过二分法找到最优解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

点击打开链接

Problem Description

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤money_i ≤ 10,000) that he will need to spend each day over the nextN (1 ≤ N ≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fa