题目名称 167. [USACO Mar07] 月度花费
输入输出 expense.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2008-10-07
开放分组 全部用户
提交状态
分类标签
USACO 分治 二分图 二分法
通过:260, 提交:936, 通过率:27.78%
Gravatarあぎめなに Love 100 0.000 s C++
Gravatar521 100 0.000 s C++
Gravatardateri 100 0.000 s C++
GravatarLCWhiStLe 100 0.000 s C++
GravatarLOSER 100 0.000 s C++
Gravatar槿柒 100 0.000 s C++
GravatarRegnig Etalsnart 100 0.000 s C++
GravatarHyoi_0Koto 100 0.000 s C++
Gravatarcy 100 0.000 s C++
GravatarRespawn 100 0.000 s C++
关于 月度花费 的讨论
和二分图有个关系
GravatarMedalPluS
2015-07-31 11:44 1楼
想不到分组的时候多分了一组居然都有70分。。。
Gravatardevil
2015-09-24 19:24 2楼
最 基本 的二分
GravatarDissolute丶Tokgo
2015-10-03 17:45 3楼
GravatarAntiLeaf
2017-05-25 15:51 4楼
神童神通
GravatarLOSER
2016-05-01 20:38 5楼
二分答案
GravatarSky_miner
2016-05-01 20:45 6楼
真的不是区域动规?
GravatarHzoi_
2016-05-01 21:08 7楼
Gravatar哒哒哒哒哒!
2017-03-12 21:35 8楼
我把所有数据答案粘下来打表 还是不如榜上的大牛快
神の无奈
GravatarSky_miner
2016-05-02 13:26 9楼
我把所有数据答案粘下来打表 还是不如榜上的大牛快
神の搞笑
Gravatar‎MistyEye
2016-05-01 21:14 10楼
我把所有数据答案粘下来打表 还是不如榜上的大牛快
神の制杖
GravatarYGOI_真神名曰驴蛋蛋
2016-05-01 21:10 11楼
我把所有数据答案粘下来打表 还是不如榜上的大牛快
神の贩剑
GravatarAntiLeaf
2016-05-01 21:10 12楼
GravatarYGOI_真神名曰驴蛋蛋
2016-05-01 21:11 13楼
我把所有数据答案粘下来打表 还是不如榜上的大牛快
神の撒币
GravatarHzoi_
2016-05-01 21:11 14楼
我把所有数据答案粘下来打表 还是不如榜上的大牛快
神の持盾
Gravatar皮波Forever
2016-05-01 21:11 15楼
神のQAQ
GravatarSOBER GOOD BOY
2016-05-01 21:13 16楼
Gravatar洛克索耶夫
2016-05-02 11:17 17楼
GravatarAntiLeaf
2017-05-25 15:52 18楼
Gravatar_Itachi
2016-05-01 21:42 19楼
Gravatar‎MistyEye
2016-05-02 17:17 20楼
膜拜楼上神犇,好神奇的区间二分查询。
Gravatar浮生随想
2016-08-11 19:16 21楼
左转917
GravatarNewBee
2016-08-11 20:42 22楼
这题各种玄学
Gravataropen the window
2016-08-17 13:06 23楼
回复 @devil :
同感
GravatarFoolMike
2016-11-01 13:37 24楼
……
GravatarTARDIS
2017-02-28 20:10 25楼
经典二分
classic
Gravatar하루Kiev
2017-08-09 21:07 26楼
多分了一组...
GravatarFisher.
2017-08-14 21:08 27楼
读入时把n读成m,m读成n,结果还过了三个点??
Gravatar八级大狂风
2017-11-07 18:51 28楼
GravatarAllforone
2017-12-14 19:38 29楼
仅仅是贴个代码
Gravatar残星誓言
2019-01-30 14:53 30楼
仅仅是贴个代码
Gravatar残星誓言
2019-01-30 14:53 31楼
仅仅是贴个代码
Gravatar残星誓言
2019-01-30 14:56 32楼

167. [USACO Mar07] 月度花费

★★   输入文件:expense.in   输出文件:expense.out   简单对比
时间限制:1 s   内存限制:128 MB

Farmer John是一个令人惊讶的会计学天才,他已经明白了他可能会花光他的钱,这些钱本来是要维持农场每个月的正常运转的。他已经计算了他以后 N(1<=N<=100,000)个工作日中每一天的花费moneyi(1<=moneyi<=10,000),他想要为他连续 的M(1<=M<=N)个被叫做“清算月”的结帐时期做一个预算,每一个“清算月”包含一个工作日或更多连续的工作日,每一个工作日都仅被包 含在一个“清算月”当中。

FJ的目标是安排这些“清算月”,使得每个清算月的花费中最大的那个花费达到最小,从而来决定他的月度支出限制。

输入

第一行:两个用空格隔开的整数:N和M 第2..N+1行:第i+1行包含FJ在他的第i个工作日的花费

输出

第一行:能够维持每个月农场正常运转的钱数

样例输入

7 5
100
400
300
100
500
101
400

样例输出

500

输入细节

这里有7个工作日来被5个“清算月”划分。他花费100,400,100,500,101,和400元在他的每个工作日。

输出细节

如果FJ安排他的月度预算,他将把前两天划分在一个月中,把第三天、第四天划分在一个月当中,最后的三个工作日各自在一个月当中,所以他一个月最多花费500元,其他的方法总是得出一个较大的结果。

100 400   300 100   500   101   400   每天花费
---1---   ---2---   -3-   -4-   -5-   月度标号
  500       400     500   101   400   月度花费