P1182 数列分段Section II

    • 2.1K通过
    • 6.6K提交
  • 题目提供者
  • 标签 二分答案 前缀和 贪心
  • 难度 普及/提高-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    对于给定的一个长度为N的正整数数列A[i],现要将其分成M(M≤N)段,并要求每段连续,且每段和的最大值最小。

    关于最大值最小:

    例如一数列4 2 4 5 1要分成3段

    将其如下分段:

    [4 2][4 5][1]

    第一段和为6,第2段和为9,第3段和为1,和最大值为9。

    将其如下分段:

    [4][2 4][5 1]

    第一段和为4,第2段和为6,第3段和为6,和最大值为6。

    并且无论如何分段,最大值不会小于6。

    所以可以得到要将数列4 2 4 5 1要分成3段,每段和的最大值最小为6。

    输入输出格式

    输入格式:

    输入文件divide_b.in的第1行包含两个正整数N,M,第2行包含N个空格隔开的非负整数A[i],含义如题目所述。

    输出格式:

    输出文件divide_b.out仅包含一个正整数,即每段和最大值最小为多少。

    输入输出样例

    输入样例#1: 复制
    5 3
    4 2 4 5 1
    输出样例#1: 复制
    6

    说明

    对于20%的数据,有N≤10;

    对于40%的数据,有N≤1000;

    对于100%的数据,有N≤100000,M≤N, A[i]之和不超过10^9。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。