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)