首页 > 试题广场 >

分组

[编程题]分组

热度指数：1619 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一个n个数字的序列 $a_1,a_2,\dots,a_n$ ，现在牛牛想把这个序列分成k段连续段，牛牛想知道分出来的k个连续段的段内数字和的最小值最大可以是多少？

示例1

输入

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

输出

说明

有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代表分出的段数
第三个参数a 包含n个元素代表n个数字

算法知识视频讲解

Python

原来是笑傲君殿下

面试太菜没有撕出来这道题诶....然后也是看了大佬们提交的答案才勉强弄明白....做一下代码的搬运工好了...思路大概如下:

首先明白我们要找的这个值一定是处于[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)

AI算法小喵

试答案法

1. 思路转换

一下想不出没关系的，我们再来问自己几个问题：

连续段段内数字之和最小是多少？
- 数组 $a$ 的最小值 $min(a)$
连续段段内数字之和最大是多少？
- 不超过数组 $a$ 的数字之和 $sum(a)$

其实，我们已经问出了一个新的遍历条件，那就是这道题答案的可能范围 $[min(a),sum(a)]$ 。

也就是说我们知道了答案的可能值最小为数组元素的最小值，最大为数组元素之和，最终的答案就在由数组元素最小值与数组元素之和框定的范围之中。到这里，我们的思路就可以转换了：从正面罗列所有可能的切分然后逐一比较，到罗列所有可能的答案再逐一排除。

2. 约束条件

我们先假设这道题的答案是answer，然后再来问自己一个问题，这个问题也就是真正的答案需要满足的条件：

$answer$ 意味着什么？
- $answer$ 是它对应的那种切法下所获得的连续段的段内数字之和的最小值。

这个答案好像是显而易见的，我们再问深一点，挖掘挖掘潜在的约束条件：

连续段段内数字之和最小，意味着什么？
- 首先，其他的连续段段内数字之和都比它大。
- 其次，以 $answer$ 为标准进行切分需要满足至少分成K段（当然可以比K多）

好了，现在我们来细致地分析下这两个约束条件条件。其他连续段段内数字之和都比 $answer$ 大，那么就有 $k*answer \le sum(a)$ 。不等式转换下就有 $k\leq\frac{sum(a)}{answer}$ ，也就是说如果我们按照和大于等于 $answer$ 作为切割条件，最终可以获得的连续段个数至少为 $k$ 。

综上分析，我们得到了一个可行的解决方法：依次尝试 $[sum(a),min(a)]$ 范围内的每一个值，并以相应值为切割条件尝试对数组 $a$ 进行切分，如果不能切成至少 $k$ 段，那么就再继续遍历。

#coding=utf-8
import sys

class Solution:
    def solve(self , n , k , a ):
        # write code here
        margin_min = min(a)
        margin_max = sum(a)
        # margin_max = int(sum(a)/k)
        for p_v in range(margin_max,margin_min-1,-1):
            tmp_sum = 0
            segment_count = 0
            for item in a:
                tmp_sum+=item
                if tmp_sum>=p_v:
                    segment_count+=1
                    tmp_sum=0

            if segment_count>=k:
                return p_v

还需补充的是其实这道题的答案范围可进一步缩小。详情可关注公众号 # AI算法小喵，参看公众号文章《一道字节算法面试题》。

链接如下：https://mp.weixin.qq.com/s?__biz=Mzg4OTY3ODQ1NQ==&mid=2247485134&idx=1&sn=4b4c6385759f683d8cf58504f9606824&chksm=cfe979d6f89ef0c09533812a0d065699cb75cda2251e4baf4610fac5a0d2029835997dcdf4e6&token=1908889430&lang=zh_CN#rd

除二分法外，公众号内还有关于这道题的回溯及动态规划解法的详细解析以及代码实现相关文章。

编辑于 2022-05-18 09:16:05 回复(0)

C/C++

nbgao

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)

Java

Yuerya

二分“试”答案法

这道题的解题思路，其实是将正面罗列出所有可能性的方式，转化成了“我知道答案的范围和约束条件，但是我不知道具体是哪一个，所以我挨个试一试”的解题方式。在“试一试”的过程中，我们用了二分查找的方式，在答案可能的范围内查找。

约束条件：

假设数组a在k段切分方式下，每段的和为Si，即S1+S2+...+Sk=S(a)
又因为这个和是k个和里最小的，所以满足条件Smin<=S(a)/k
当想要Smin在所有切分方式中最大时，数组的切分会逐渐均匀（即每段和趋于一致），Smin会向S(a)/k逼近。
我们需要做的，就是依次尝试[0, S(a)/k]中的每一个值，看在数组尽量均匀被切分的情况下（即按顺序遍历数组，元素和达到这个值时就切断），能不能被切成K段。
如果能切分，说明我们还可以往更大的数试试。如果不能，就说明太大了，减小答案再试试。

import java.util.*;

public class Solution {
    public int solve (int n, int k, int[] a) {
        if(a.length == 0){
            return 0;
        }
        int sum = 0;
        for(int i = 0; i < n; i ++){
            sum  = sum + a[i];
        }
        if(k == 1){
            return sum;
        }
        int low = 0;
        int high = sum/k;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(check(a, k, mid)){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return (low+high)/2;
    }
    public boolean check(int a[], int k, int min_max_sum){
        int count = 0;
        int sum = 0;
        for(int j = 0; j < a.length; j++){
            sum += a[j];
            if(sum >= min_max_sum){
                sum = 0;
                count += 1;
                if(count >= k){
                    return true;
                }
            }
        }
        return false;
    }
}

发表于 2021-04-02 01:21:16 回复(0)

胖墩墩的小熊猫准备进厂

有没有大神详细的解释一下这一句是什么含义呢？什么最小值的最大值有点晕😪

for i in a:
    sum_+=i
    if sum_>=mean_:
       seg+=1
       sum_=0

发表于 2020-12-04 10:41:10 回复(0)

ac_q

垃圾的我在刷二分 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)

C/C++

萨巴鲁酱

参考前面大佬的思路，对最后一步改进了一下

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)