P1182 数列分段 Section II

提交 34.77k
通过 11.79k
时间限制 1.00s
内存限制 125.00MB
题目提供者 洛谷
历史分数100

提交记录

查看题解

标签

 
查看算法标签
进入讨论版

相关讨论

 
查看讨论

推荐题目

 
查看推荐
 

展开

题目描述

对于给定的一个长度为N的正整数数列 A1∼NA_{1\sim N}A1∼N​，现要将其分成 MMM（M≤NM\leq NM≤N）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 4 2 4 5 14\ 2\ 4\ 5\ 14 2 4 5 1 要分成 333 段。

将其如下分段：

[4 2][4 5][1][4\ 2][4\ 5][1] [4 2][4 5][1]

第一段和为 666，第 222 段和为 999，第 333 段和为 111，和最大值为 999。

将其如下分段：

[4][2 4][5 1][4][2\ 4][5\ 1] [4][2 4][5 1]

第一段和为 444，第 222 段和为 666，第 333 段和为 666，和最大值为 666。

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

所以可以得到要将数列 4 2 4 5 14\ 2\ 4\ 5\ 14 2 4 5 1 要分成 333 段，每段和的最大值最小为 666。

输入格式

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

第 222 行包含 NNN 个空格隔开的非负整数 AiA_iAi​，含义如题目所述。

输出格式

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

输入输出样例

输入 #1 
5 3
4 2 4 5 1
输出 #1 
6

 

 

思路

　　要求最大值最小，二分即可。因为要求段的最大值所以在 max a[i] ~ sum a[i] 中二分答案。

　　如果在 1 ~ sum a[i] 中二分会WA4，调了半个多小时不知道为什么，翻了翻题解也没人解释。。。

 

CODE

 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 #define pi acos(-1.0)
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 template<class T>inline void read(T &res)
10 {
11     char c;T flag=1;
12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
14 }
15 
16 namespace _buff {
17     const size_t BUFF = 1 << 19;
18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
19     char getc() {
20         if (ib == ie) {
21             ib = ibuf;
22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
23         }
24         return ib == ie ? -1 : *ib++;
25     }
26 }
27 
28 int qread() {
29     using namespace _buff;
30     int ret = 0;
31     bool pos = true;
32     char c = getc();
33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
34         assert(~c);
35     }
36     if (c == '-') {
37         pos = false;
38         c = getc();
39     }
40     for (; c >= '0' && c <= '9'; c = getc()) {
41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
42     }
43     return pos ? ret : -ret;
44 }
45 
46 const int maxn = 1e5 + 7;
47 
48 int n,k;
49 int a[maxn];
50 int ans;
51 int maxx;
52 
53 inline bool check(int x) {
54     int tot = 0, cnt = 0;
55     for ( int i = 1; i <= n; ++i ) {
56         if(tot + a[i] <= x) {
57             tot += a[i];
58         }
59         else {
60             tot = a[i];
61             cnt++;
62         }
63     }
64     if(cnt >= k) {
65         return true;
66     }
67     return false;
68 }
69 
70 int main()
71 {
72     int l = 0, r = 0, mid;
73 
74     scanf("%d %d",&n, &k);
75     for ( int i = 1; i <= n; ++i ) {
76         scanf("%d",&a[i]);
77         l = max(l, a[i]);
78         r += a[i];
79     }
80     //l = 1, r = 1e9;
81     mid = (l + r) >> 1;
82     while( l <= r) {
83         mid = (l + r) >> 1;
84         if(check(mid)) {
85             l = mid + 1;
86         }
87         else {
88             r = mid - 1;
89         }
90     }
91     printf("%d\n",l);
92     return 0;
93 }
View Code