首页 > 贝壳-210813-1
头像
KKKAREN
发布于 2021-08-14 01:50
+ 关注

贝壳-210813-1

n行田地m值浇水

题目描述

有n行田地,m值的水量,从1浇道n行,再返回浇水(即从n-1浇到1),直到水没有,求每行水量,如4行田地,6值的水量,结果应为[1,2,2,1]

题解1

import sys
def Solution():
    """
    2021-08-13 
    n lines with m bread, put bread in lines
    :rtype: list 
    """
    for line in sys.stdin:
        a = line.strip().split(',')
        a = [int(i) for i in a]
        m = a[0]
        n = a[1]

        ret_list = [0]*n

        while m > 0:
            for i in range(0,2*n-2):
                if i in range(0,n):
                    ret_list[i] = ret_list[i] + 1
                else:
                    index = -i+n-2
                    ret_list[index] = ret_list[index] + 1
                m = m - 1

                if m <= 0:
                    break
        print(ret_list)

        return ret_list
Solution()
  • 思路:将问题转化为给[0,2n-2]行田地浇水,直到水量为0
  • 分析:实际通过率只有10%,该方法时间复杂度过高

题解2

import sys

def Solution():

    for line in sys.stdin:
        a = line.strip().split(',')
        a = [int(i) for i in a]
        m = a[0]
        n = a[1]

        ret_list = [0] * n 
        real_n = 2*n - 2

        group_num = m // real_n
        rest_num = m % real_n

        for i in range(1,n-1):
            ret_list[i] = group_num*2
        ret_list[0] = group_num
        ret_list[n-1] = group_num

        signal_val = 1
        i = 0

        while rest_num > 0:
            ret_list[i] = ret_list[i] + 1
            rest_num = rest_num - 1
            if signal_val:
                i = i + 1
                if i == n - 1:
                    signal_val = 0
            else:
                i = i - 1

        print(ret_list)
        return ret_list

Solution()
  • 参考了该帖子
  • 取整m//(2n-2),将取整的结果直接填到待求数组中,ret_list[1:n-2]为2*取整结果,ret_list[0]和ret_list[n-1]为取整结果
  • 将余数填到待求数组中,利用flag标记控制数组上升下降方向
  • 时间复杂度降低,为o(n)

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐