首页 > 试题广场 > 分组
[编程题]分组
  • 热度指数:1194 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛有一个n个数字的序列,现在牛牛想把这个序列分成k段连续段,牛牛想知道分出来的k个连续段的段内数字和的最小值最大可以是多少?
示例1

输入

4,2,[1,2,1,5]

输出

4

说明

有3种分法
[1],[2,1,5],数字和分别为1,8,最小值为1
[1,2][1,5],数字和分别为3,6,最小值为3
[1,2,1],[5]数字和分别为4,5,最小值为4
则最小值的最大值为4

备注:


第一个参数整数n代表序列数字个数
第二个参数整数k代表分出的段数
第三个参数vector a 包含n个元素代表n个数字
面试太菜没有撕出来这道题诶....然后也是看了大佬们提交的答案才勉强弄明白....做一下代码的搬运工好了...思路大概如下:
首先明白我们要找的这个值一定是处于[0,sum(a)]这个区间的一个值,但具体是多少不知道.
那么我们首先可以判断mid1 = sum(a)/2这个值能不能划分出大于等于k个组,
如果可以那么我们其实可以缩小区间至[mid1,sum(a)],再次判断mid2 = (sum(a)+mid1)/2 能否得到k个组.如果不可以,那自然的,只能将区间改写为[mid1,mid2],
依次循环直到某一时刻.我们找到一个能将整个组划分为k个且对应区间的左右两端差值极小.(理论上小于1就可以.)
那么这个时候,自然的我们就找到了对应可以划分出来的数字和的最大最小值.(均分情况下明显最小值会大于别的情况嘛~)
#
# 分组
# @param n int整型 
(4640)# @param k int整型 
# @param a int整型一维数组 
(4641)# @return int整型
#
class Solution:
    def solve(self, n, k, a):
        x, y = 0, sum(a)
        if k == 1:
            return y
        while y - x > 1:
            mid = (x + y) / 2
            segment = 0
            nowval = 0
            for i in range(len(a)):
                nowval += a[i]
                if nowval >= mid:
                    segment += 1
                    nowval = 0
            if segment >= k:
                x = mid
            else:
                y = mid
        return round((x + y) / 2)
发表于 2020-04-08 23:21:42 回复(3)
class Solution {
public:
    /**
     * 分组
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int k, vector<int>& a) {
        int l=0, r = 0, m, cnt, t;
        for(int i=0;i<n;i++)
            r += a[i];
        if(k==1)
            return r;
        while(l+1<r){
            m = (l+r)>>1;
            cnt = t = 0;
            for(int i=0;i<n;i++){
                t += a[i];
                if(t>=m){
                    cnt++;
                    t = 0;
                }
            }
            if(cnt>=k)
                l = m;
            else
                r = m;
        }
        return (l+r)>>1;
    }
};

发表于 2020-06-25 02:19:15 回复(0)
垃圾的我在刷二分 6-29
```cpp
class Solution {
public:
    /**
     * 分组
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return int整型
     */
    bool check(vector<int>& a, int v, int tar)
    {
        int k = 1;
        int sum = 0;
        for(int i = a.size() - 1; i >= 0; i--)
        {
            sum += a[i];
            if(sum > v)
            {
                k++;
                sum = 0;
            }
        }
        return k <= tar; //分的包的mid容量大, 包的数量k  小于等于目标值tar 是合法的
    }
    int solve(int n, int k, vector<int>& a) {
        int  left = 0;
        int  right = 0;
        for(int i = 0; i < a.size(); i++)
        {
            left = min(a[i],left);
            right += a[i];
        }
       
        while(left < right)
        {
            int mid = (left + right) / 2;
            if(check(a,mid,k))
            {
                right = mid;
            }
            else
            {
                 left = mid + 1;
            }
            
        }
        return left;
        
    }
};

发表于 2020-06-29 15:09:20 回复(0)
参考前面大佬的思路,对最后一步改进了一下
class Solution {
public:
    /**
     * 分组
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int k, vector<int>& a) {
        int low = 0, high = 0;
        for(auto i : a){
            high += i;
        }
        while(high - low > 1){
            int mid = low + ((high - low) >> 1);
            int sum = 0;
            int nGroup = 0;
            for(auto i : a){
                sum += i;
                if(sum >= mid){
                    nGroup += 1;
                    sum = 0;
                }
            }
            if(nGroup >= k)
                low = mid;
            else
                high = mid;
        }

        int sum = 0;
        int nGroup = 0;
        for(auto i : a){
            sum += i;
            if(sum >= high){
                nGroup += 1;
                sum = 0;
            }
        }

        return (nGroup >= k)? high : low;
    }
};


发表于 2020-05-19 02:25:10 回复(0)
二分。。。
发表于 2020-04-22 23:09:51 回复(0)