数列分段【二分】_求一个数列的所有前缀最大值之和。即:给出长度为 n 的数列 a i ,-程序员宅基地

题目大意：

给出一个数字串，将它分成 $m$ 个部分，要求每个部分的和的最大值最小。

思路：

很明显的二分答案。首先利用前缀和求出前 $i$ 个数字之和，然后 $l=1,r=s[n]$ 来二分和的最大值。要注意当任意一个 $s[i]-s[i-1]>m$ 那么就必然不成立。

代码：

#include <cstdio>
#include <iostream>
using namespace std;

int n,m,s[100011],l,r,mid,sum,k;

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        s[i]+=s[i-1];  //前缀和
    } 
    l=1;
    r=s[n];
    while (l<r)
    {
        mid=(l+r)/2;
        sum=0;
        k=0;
        for (int i=1;i<=n;i++)
        {
            if (s[i]-s[i-1]>mid)  //任意一个数字超过了答案
            {
                sum=m+1;
                break;
            }
            if (s[i]-s[k]>mid)  //这一部分超过答案
            {
                sum++;
                k=i-1;
                if (sum>m) break;
            }
        }
        if (sum<m) r=mid;
         else l=mid+1;
    }
    printf("%d\n",r);
    return 0;
}

本文链接：https://blog.csdn.net/SSL_ZYC/article/details/81629828

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【xamarin】xamarin debug exited-程序员宅基地

文章浏览阅读297次。https://forums.xamarin.com/discussion/3304/debugger-fails-to-start-the-program-mono-has-exited-with-code-0-0x0

dedecms织梦会员模板调用全站head.htm模板-程序员宅基地

文章浏览阅读207次。第一步：打开"/include/common.func.php"，该文件5.6版本默认存在，5.5的不存在自己建一个。然后在该文件中加入一个函数，代码如下：function pasterTempletDiy($path){ require_once(DEDEINC."/arc.partview.class.php"); global $cfg_basedir,$cfg_templet..._php调用htm模版

解决Ubuntu 14.04 重启后DNS配置丢失(resolv.conf丢失)的问题_/etc/resolv.conf 不存在-程序员宅基地

文章浏览阅读3.3k次。问题从网上得知 /etc/resolv.conf中的DNS配置是从/etc/resolvconf/resolv.conf.d/head中加载而来,所以每回改resolv.conf都会失效，在此文件里面已经有说明打开/etc/resolv.conf内容如下：jie@jie:~$ cat /etc/resolv.conf# Dynamic resolv.conf(5) file for gli..._/etc/resolv.conf 不存在

启动SQL Server Agent服务（开机启动）_sqlserver2012agent-程序员宅基地

文章浏览阅读3.1w次，点赞4次，收藏8次。启动SQL Server Agent服务（开机启动）方法一、在命令提示符下，输入下列命令之一：net start "SQL Server Agent (MSSQLSERVER)" （这个无法使用）- 或 -net start SQLSERVERAGENT （我是用这个启动的）方法二、_sqlserver2012agent

java怎么学才能学好？-程序员宅基地

文章浏览阅读653次，点赞2次，收藏4次。java怎么学才能学好？IT行业近年来的发展可谓是相当不错，java程序员更是最受欢迎的职业，很多想进入IT行业的朋友都会选择学习java，因为它的应用广泛，就业机会比较多，但是他们都比较关心一个问题，那就是java应该怎么学才好？1、学好基本语法，明确Java的特点学习java语言就是学习语法、函数、结构等，根据java语法编写代码。语法是学习Java的基础。在学习之初可能很难理解。没问题。这是正常现象。你必须多读，多问，多练习。你会慢慢开始学习的。2、代码上添加注释，来解释代码注释的功能_java怎么学才能学好

GTK+ 多线程_gtk多线程-程序员宅基地

文章浏览阅读1.2k次。GTK+ 多线程操作操作 UI 元素时，早期一般都是使用gdk_thread_enter() / gdk_thread_leave() 来进行线程间同步。但是 GTK+ 3.6 开始，不建议使用该函数对。仔细考虑下，似乎有些道理。频繁的调用gdk_thread_enter() / gdk_thread_leave()确实影响 GTK+ 的性能，并且容易出现莫名的错误。但是，如何解决在多_gtk多线程

随便推点

CI框架源码研读(整体架构)_ci 框架超级类-程序员宅基地

文章浏览阅读2.9k次。有人说phper的深入要从研读mvc框架开始，我跳了一个常用的CI框架入手，一是因为 CI框架简单轻巧，二是原来用的最多的就是CI框架了。 1、首先来看CI的整体架构图：上图中是我最新下载CI3.0版本，application是用户级开发目录，我们关心system系统源码目录，CI的核心代码都在这里了。1、core 系统核心代码2、database数据库_ci 框架超级类

山东省第五届蓝桥杯 ///标题：啤酒和饮料//c/c++组-程序员宅基地

文章浏览阅读439次。标题：啤酒和饮料啤酒每罐2.3元，饮料每罐1.9元。小明买了若干啤酒和饮料，一共花了82.3元。我们还知道他买的啤酒比饮料的数量少，请你计算他买了几罐啤酒。注意：答案是一个整数。请通过浏览器提交答案。不要书写任何多余的内容（例如：写了饮料的数量，添加说明文字等）。______________________

MVC（模型-控制器-视图）架构模式（下）_enableoptimizations-程序员宅基地

文章浏览阅读141次。MVC架构模式常见问题1、MVC的路由选择功能是帮你定义一个URL规则，映射URL到控制器。在“global.asax“文件中写路由映射表。2、可以映射多个URL到同一个映射，只需要添加多条不同Key名字的记录，并且指定同样的控制器和动作。3、使用hyperlink生成连接，可以通过使用ActionLink方法从一个视图链接到另一个视图。4、在MVC中可以通过tempdata，viewdata和viewbag来保持sessions。Temp data -在不同的控制器或动作间转换时保持._enableoptimizations