文档章节

洛谷:P1182:数列分段`Section II`

o
 osc_4nmshwhm
发布于 2018/08/06 21:50
字数 849
阅读 8
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目描述

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

关于最大值最小:

例如一数列 4 2 4 5 142451 要分成 33 段

将其如下分段:

[4 2][4 5][1][42][45][1]

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

将其如下分段:

[4][2 4][5 1][4][24][51]

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

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

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

输入输出格式

输入格式:

第 1 行包含两个正整数N,M。

第 22行包含 NN 个空格隔开的非负整数 Ai ,含义如题目所述。

 

输出格式:

一个正整数,即每段和最大值最小为多少。

 

输入输出样例

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

说明

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

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

对于 100\%100% 的数据,有 N≤100000,M≤N, Ai,Ai 之和不超过 10^9 。


 

  这个题时一个典型的二分答案(最大的最小、最小的最大)

  首先根据题意,我们确定段的最大值一定在整个数组的最大值和10^9之间,因此做如下定义

   l = maxn, r = 1000000000; 

  然后我们确定好一个mid = (l+r)>> 1,表示最大值为mid时是否可行;

  下面就进行二分的正常过程,判断

  然后遍历整个数列,记录下一个tot,表示这个数列中最大值不超过mid时,需要分成的段数,用now来代表当前段的和

 

  now+a[i]<mid时:可以继续加,这个段还没有结束

  now+a[i]==num时:说明当前段已经达到了最大值,记下这个段(tot++),now=0,以便分析下一个段

  now+a[i]>num时:说明这个段加上a[i]之后超过mid,就不能加上这个a[i],那么这个段已经计算完(tot++),a[i]算到下一个段内

  

  如果tot<m,说明要达到当前的段数m,mid的值必须要降低,这样才能使段数增多,收缩右边界;

  否则,改变左边界。

  

  附上代码(亲测AC)

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 const int MAXN=100001;
 5 int maxn = -1;
 6 int n, m, a[1000010];
 7 int l = maxn, r = 1000000000;
 8 int judge(int num){
 9     int now = 0;
10     int tot = 0;
11     for(int i=1;i<=n;i++){
12         if(now+a[i]<num){
13             now += a[i];
14         }
15         else if(now+a[i]==num){
16             now = 0;
17             tot++;
18         }
19         else if(now+a[i]>num){
20             now = a[i];
21             tot++;
22         }
23     }
24     if(now) tot++;  //如果还有剩余的一个值,那么这个单独算一个段
25     if(tot>m)return 0;
26     else return 1;
27     
28 }
29 
30 int main(){
31     cin >> n >> m;
32     for(int i=1;i<=n;i++) {
33         cin >> a[i];
34         maxn = max(a[i], maxn);
35     }
36     int l = maxn, r = 1000000000;     
37     if(n==m){
38         cout << maxn;
39         return 0;
40     }
41     while(l<r){
42         int mid = (l+r) >> 1;
43         if(judge(mid)==1){
44             r = mid;
45         }
46         else{
47             l = mid + 1;
48         }
49     }
50     cout << r;
51     return 0;
52 }

 

下一篇: 我的书单
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

jQuery获取select onChange的值 - jQuery get value of select onChange

问题: I was under the impression that I could get the value of a select input by doing this $(this).val(); 我的印象是我可以通过执行$(this).val();来获取选择输入的值$(this).val()......

javail
35分钟前
13
0
道翰天琼解密宇宙信息大脑三者最核心奥秘,破解认知智能基础理论(群聊形式)

三体论是探索研究宇宙,信息和人类大脑三者关系的理论体系。是认知智能的奠基理论体系之一。宇宙和信息,信息和人类大脑,人类大脑和宇宙,三者之间存在着某种未被完全揭示的奥秘。三体论的核...

jackli2020
37分钟前
15
0
OSChina 周日乱弹 —— 这些照片能留存下来要感谢蛇不吃相机

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《28》- ゴンチチ 手机党少年们想听歌,请使劲儿戳(这里) @FalconChen :真得学...

小小编辑
44分钟前
76
0
如何在视频中的对象后面添加图像

作者|PRATEEK JOSHI 编译|VK 来源|Analytics Vidhya 概述 在运动物体后面添加图像是一个典型的计算机视觉项目 了解如何使用传统的计算机视觉技术在视频中添加logo 介绍 我的一位同事向我提出...

人工智能遇见磐创
48分钟前
14
0
UKUI Desktop Environment

install $ sudo add-apt-repository ppa:ubuntukylin-members/ukui3.0$ sudo apt upgrade or $ sudo apt-get install curl$ curl -sL 'https://keyserver.ubuntu.com/pks/lookup?&op=get&......

qwfys
52分钟前
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部