数字拆分消减问题

题目

给出两个数字

n

,

k

n,k

$n, k$ (

n

,

k

∈

N

+

n,k \in \N^+

$n, k \in N^{+}$ )。

n

n

$n$ 是需要拆分消减的数字序列(初始情况序列仅包含一个数字)，

k

k

$k$ 是最多可拆分的次数，其中：

拆分是指将一个数字的拆分序列中的每个数字 $a_1 a1、 a 2 a_2 a2且 a 1 + a 2 = a a_1+a_2=a a1+a2=a；$

效减是秩将所有拆分得到的数字减去1；

e.g : 对数字序列[7]先拆分两次再消减一次——第一次拆分得到[4, 3]、第二次拆分得到[2, 2, 1, 2]，消减后得到[1, 1, 0, 1]。
问：输入

n

,

k

n,k

$n, k$ ，请输出能把序列变为全0序列的最少次数。

分析

要使得其最快为0，显然应进行尽量多的平均拆分再进行消减。由于数字2先拆分后消减与先消减再拆分到0都需要2步，因此平均到数列中出现2即可停止。
在任意一次平均拆分结束后，如果出现奇数，则意味着下一次拆分必然会出现

若出现奇数：消减次数 =
若未出现奇数或本身未进行拆分：消减次数 =

代码

is_odd = lambda x: x % 2 == 1

for nk in nk_list:
    n, k = nk[0], nk[1]
    _min = n  #
    found_odd = is_odd(n)
    divide_done = 0  # 拆分进行次数
    for _ in range(k):
        if _min <= 2:
            break
        found_odd = is_odd(_min)
        _min = _min // 2
        divide_done += 1

    if divide_done > 0 and found_odd:
        _min += 1

    print(divide_done+_min)

测试数据：

# 输入数据
# 输出应为 0 1 1 2 2 5 6 16 8
nk_list = [[0, 7], [1, 0], [1, 2], [2, 1], [2, 3], [15, 3], [16, 2], [100, 3], [100, 7]]

单链路村庄销售代价问题

题目

在一条直线公路上，等距分布着

n

n

$n$ 个村庄(n为大于1的自然数)，第

i

i

$i$ 个村庄有

s

i

s_i

$s_{i}$ 的水果要销售或购入，当

s

i

<

0

s_i<0

$s_{i} < 0$ 则意味着要购入

s

i

s_i

$s_{i}$ 个水果，当

s

i

>

0

s_i>0

$s_{i} > 0$ 则意味着要卖出

s

i

s_i

$s_{i}$ 个水果。已知每个水果每向旁别的存在运输一次，就产生

1

1

$1$ 个单位的代价。先给出一组数据，保证整条公路上的水果供求关系的和为0，问要使每个村庄完成购入/卖出指标，最小代价为多少。
e.g 例如输入[1, 0, -1]，则最小代价为

4

4

$4$ 。

分析

由于所有村庄等距分布在一条公路上，因此当我们从左往右遍历数组，会发现无论左边是正是负，必然需要被“抹平”。

假设有这么一个堆(heap)，存放着“水果债卷”，一个商人从走往右走，对这个堆进行分配和移动。
每到一个村庄，商人先按照供需关系修改堆中的债券关系，如果 $s_i>0 si>0，则堆中债券变多，否则变少。$
随后，商人根据债卷的价值产生移动水果的代价。如果 $s_i>0 si>0，则意味着左边有数量为 s i s_i si的水果要移动到右边，否则意味着右边有数量为 s i s_i si的水果要移动到左边。$
无论向左还是向右移动，最终都会产生

代码

def count(data):
    heap, cost = 0, 0
    for i in data:
        heap += i
        cost += abs(heap)
    return cost

测试：

s1 = [1, -1, 2, 0, -2, -4, 1, 3]  # 12
s2 = [-1, -2, -3, 0, 1, 2, 3]  # 24
s3 = [1, 2, 3, 0, -1, -2, -3]  # 24
s4 = [1, -1, 0]  # 1
s5 = [-1, 1, 0]  # 1
s6 = [2, 0, -2]  # 4

print(count(s1))
print(count(s2))
print(count(s3))
print(count(s4))
print(count(s5))
print(count(s6))