题解 | #分组#
分组
http://www.nowcoder.com/practice/829419bde0e946b6b4fe813ed3972db8
题意：
给定n个数字的序列
，现在想把这个序列分成k段连续段，想知道分出来的k个连续段的段内数字和的最小值最大可以是多少？
方法一：
贪心
思路：计算a[]数组之和sum,则是该问题的理想情况的最大值。
因此可以贪心，以
判断该值是否满足情况：如果满足，则return。
class Solution {
public:
int solve(int n, int k, vector<int>& a) {
int sum=0;//sum是a数组之和
for(int i=0;i<n;i++){
sum+=a[i];
}
for(int i=sum/k;i>=0;i--){//贪心,值从大到小遍历
if(f(a,k,i))//如果成功，return
return i;
}
return 0;
}
int f(vector<int>& a,int k,int x){
int n=a.size();//a数组长度
int s=0;//初始和为0
for(int i=0;i<n;i++){
s+=a[i];
if(s>=x){
s=0;
k--;//段数减一
if(k==0)//如果达到k段，则成功
return 1;
}
}
return 0;
}
};
时间复杂度：%2Csum%E6%98%AFa%5B%5D%E4%B9%8B%E5%92%8C%EF%BC%8Ck%E6%98%AF%E6%AE%B5%E6%95%B0%EF%BC%8Cn%E6%98%AFa%5B%5D%E6%95%B0%E7%BB%84%E4%B8%AA%E6%95%B0)
空间复杂度：%2C%E4%B8%8D%E9%9C%80%E8%A6%81%E9%A2%9D%E5%A4%96%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4)
方法二：
二分
思路：可以将方法一的贪心算法二分化。设L=0,R=如果满足判断，则(扩大数值)
否则(缩小数值)
class Solution {
public:
int solve(int n, int k, vector<int>& a) {
int sum=0;//sum是a数组之和
for(int i=0;i<n;i++){
sum+=a[i];
}
int l=0,r=sum/k,mid;
while(l<r){
mid=(l+r+1)/2;
if(f(a,k,mid))//如果满足，则l=mid
l=mid;
else//否则，r=mid-1
r=mid-1;
}
return l;
}
int f(vector<int>& a,int k,int x){
int n=a.size();
int s=0;//初始和为0
for(int i=0;i<n;i++){
s+=a[i];
if(s>=x){
s=0;
k--;//段数减一
if(k==0)//如果达到k段，则成功
return 1;
}
}
return 0;
}
};
时间复杂度：)%2Cn%E6%98%AF%E6%95%B0%E7%BB%84%E5%85%83%E7%B4%A0%E4%B8%AA%E6%95%B0%EF%BC%8Csum%2Fk%E6%98%AF%E7%90%86%E6%83%B3%E4%B8%AD%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC%E3%80%82)
空间复杂度：
顺丰集团工作强度 307人发布