| 题目名称 | 3171. [POJ 3017]Cut the Sequence |
|---|---|
| 输入输出 | cutsequence.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 12 |
| 题目来源 |
 LGLJ
于2019-06-13加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：15， 提交：21， 通过率：71.43% | ||||
 嗨嗨嗨 |
100 | 0.005 s | 1.33 MiB | C++ |
|
舛 |
100 | 0.007 s | 0.73 MiB | C++ |
|
舛 |
100 | 0.012 s | 0.73 MiB | C++ |
|
舛 |
100 | 0.014 s | 0.73 MiB | C++ |
|
liuyiche |
100 | 0.014 s | 1.34 MiB | C++ |
 LGLJ |
100 | 0.018 s | 0.52 MiB | C++ |
|
LGLJ |
100 | 0.018 s | 1.04 MiB | C++ |
|
在大街上倒立游泳 |
100 | 0.021 s | 0.73 MiB | C++ |
|
whaleeee |
100 | 0.039 s | 0.73 MiB | C++ |
|
健康铀 |
100 | 0.047 s | 0.92 MiB | C++ |
| 关于 Cut the Sequence 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
n^2能过是真逆天
健康铀
2023-12-07 20:42
1楼
| ||||
3171. [POJ 3017]Cut the Sequence
★★★ 输入文件：cutsequence.in
输出文件：cutsequence.out
简单对比时间限制：2 s 内存限制：128 MiB
【题目描述】
给定一个长度为 $N$ 的序列 $A$ ,要求把该序列分成若干段，在满足“每段中所有数的和”不超过 $M$ 的前提下，让“每段中所有数的的最大值”之和最小。
计算这个最小值。
【输入格式】
第一行两个整数，表示 $N$ 和 $M$
第二行 $N$ 个整数，表示 $A_i$
【输出格式】
所求的最小值，如果不存在此类方法，则输出-1
【样例输入】
8 17 2 2 2 8 1 8 2 1
【样例输出】
12
【提示】
$N<=10^5$
数列中 $A$ 中的数非负，且不超过 $10^6$
$M<=10^{11}$
PS:数据还是很水，希望同学们还可以再在POJ上评测一遍，以保证代码的正确。
【来源】
《算法竞赛进阶指南》 POJ 3017