发现
问答
发起
提问
文章
文章
更多
专家
话题
财富榜
商城
Toggle navigation
首页
(current)
问答
文章
话题
商城
搜索
登录
注册
问码农们一个算法问题。
中一小朋友,competitive programming / binary search 内容中的一个练习题。简化一下问题描述:
一个连续数列,比如 1 2 3 4 5 6 7 8 9 ... m 分成 n 个相连的 group,每种分法,取最大的那个 group sum。 问,怎么分,才有最小的最大 group sum。
比如 m = 9, 1 2 3 4 5 6 7 8 9 n = 3 分成 3 组 A) 分成 (1 2) (3 4) (5 6 7 8 9) -> max sum: 5+6+7+8+9=35 B) 分成 (1 2 3) (4 5 6) (7 8 9) -> max sum: 7+8+9=24 C) 分成 (1 2 3 4 5) (6 7) (8 9) -> max sum: 8+9=17 D) ......
答案是 17,不管怎么分,最小的 max sum 是 17,C 的那种分法。
test case,取不同的 m, n, 并且 0 < m, n < 1000。 不光看答案,也看运行时间。
暴力测试是可以的,但是运行时间超时 (AWS 上编译的 C++ 代码)。 我觉得这样的题目给中一孩子太难了。而且也没弄懂怎么在上面应用 binary search。 还是想得太复杂?
0 条评论
分类:
闲聊
请先
登录
后评论
默认排序
时间排序
2 个回答
单于和宁
2019-07-12 19:46
划分型动态规划
我瞎编的...
请先
登录
后评论
梅楠义
2019-07-12 19:46
这个题目没看懂
1. 如果是有序数列,就不需要binary search,排序才需要
2. 不知道理解对不对,按照字面理解,既然至少需要两个数做group,找出最大两个数即可,然后计算和
3. 如果2理解是对的,而且是个无序数组,只要找出数组中两个最大的数字即可。算法很简单,一遍扫描就可以完成了,不需要binary search。
建议把英文原题贴出来吧,方便理解。
请先
登录
后评论
您需要登录后才可以回答问题,
登录
或者
注册
关注
0
关注
收藏
0
收藏,
594
浏览
印亚妮
提出于 2019-07-12 19:46
相似问题
×
发送私信
发给:
内容:
×
举报此文章
垃圾广告信息:
广告、推广、测试等内容
违规内容:
色情、暴力、血腥、敏感信息等内容
不友善内容:
人身攻击、挑衅辱骂、恶意行为
其他原因:
请补充说明
举报原因: