分组

[编程题]分组

热度指数：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)