数组划分游戏 HihoCoder - 1948 (二分答案)

题目

https://cn.vjudge.net/problem/HihoCoder-1948

小Hi在玩一个有关数组划分的游戏。给定一个整数K和一个长度为N的数组A=[A1, A2, … AN],小Hi需要将它划分为K个连续子数组,并对每个子数组求和。

不妨设这K个子数组的和依次是S1, S2, … SK,则小Hi的得分是其中的最小值即min(S1, S2, … SK)。

例如对于A=[1, 2, 3, 4]和K=2,小Hi可以划分成[1, 2]和[3, 4],这样得分是3;也可以划分成[1, 2, 3]和[4],这样得分是4。

对于给定的K和数组A,你能帮助小Hi算出他最多能得多少分吗?

Input
第一行包含两个整数N和K。

第二行包含N个整数A1, A2, … AN。

对于60%的数据,1 <= N <= 1000

对于100%的数据,1 <= K <= N <= 100000 1 <= Ai <= 1000000

Output

一个整数代表答案

Sample Input

1
2
4 2
1 2 3 4

Sample Output
1
4

思路

通过这个题总算明白了二分答案是怎么一回事了。

二分答案,即假设已经知道了答案,拿这个已知的答案去验证题目要求是否满足。二分答案就是在答案的可能选择的区间内,二分地枚举每一个答案是否满足题目要求,将最优性问题(难以解决)转化为可行性问题。

而这个题目,就是枚举每个可能地得分数,然后看按照这个得分数,数组能否被划分为指定的段数,如果能,这即是答案,如果不能,接着二分枚举。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN=1e5+10;

ll arr[MAXN];
ll n,m;
ll Min=0x3f3f3f3f,Sum=0;

ll check(ll x)
{
ll ans=0,tmp=0;
for(int i=1;i<=n;i++) {
tmp+=arr[i];
if(tmp>=x) ans++,tmp=0;
}
return ans;
}
int main()
{
// cout<<(1<<30)<<endl<<(0x3f3f3f3f)<<endl;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%lld",&arr[i]);
Min=min(Min,arr[i]);
Sum+=arr[i];
}
ll l=Min,r=2*Sum;
while(l<=r) {
if(l+1==r) break;
ll mid=(l+r)/2;
ll q=check(mid);
if(q<m) r=mid;
else l=mid;
}
printf("%lld\n",l);
return 0;
}

/*
3 2
1 2 3

*/