[编程题]塔
  • 热度指数:20288 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小易有一些立方体,每个立方体的边长为1,他用这些立方体搭了一些塔。
现在小易定义:这些塔的不稳定值为它们之中最高的塔与最低的塔的高度差。
小易想让这些塔尽量稳定,所以他进行了如下操作:每次从某座塔上取下一块立方体,并把它放到另一座塔上。
注意,小易不会把立方体放到它原本的那座塔上,因为他认为这样毫无意义。
现在小易想要知道,他进行了不超过k次操作之后,不稳定值最小是多少。

输入描述:
第一行两个数n,k (1 <= n <= 100, 0 <= k <= 1000)表示塔的数量以及最多操作的次数。
第二行n个数,ai(1 <= a<= 104)表示第i座塔的初始高度。


输出描述:
第一行两个数s, m,表示最小的不稳定值和操作次数(m <= k)
接下来m行,每行两个数x,y表示从第x座塔上取下一块立方体放到第y座塔上。
示例1

输入

3 2
5 8 5

输出

0 2
2 1
2 3
def solution(k, hights):
    count = 1
    operation = []  # 存储操作步骤
    unstability = max(hights) - min(hights)
    while unstability > 1 and count <= k:
        maxhight_index = hights.index(max(hights))
        minhight_index = hights.index(min(hights))
        hights[maxhight_index] -= 1
        hights[minhight_index] += 1
        count += 1
        operation.append([maxhight_index+1, minhight_index+1])
        maxhight = max(hights)
        minhight = min(hights)
        unstability = maxhight - minhight
    count -= 1
    print(unstability, count)
    for i in operation:
        print(i[0], i[1])
if __name__ == '__main__':
    n, k = list(map(int, input().strip().split()))
    hights = list(map(int, input().strip().split()))
    solution(k, hights)

发表于 2020-06-16 12:37:30 回复(0)
n, k = map(int, input().strip().split())
h = list(map(int, input().strip().split()))
unstable = max(h) - min(h)
operation = []
times = 0
for i in range(k):
    max_idx, max_h = max(enumerate(h), key = lambda x:x[1])
    min_idx, min_h = min(enumerate(h), key = lambda x:x[1])
    if max_h - min_h >= 2:
        operation.append((max_idx, min_idx))
        h[max_idx] -= 1
        h[min_idx] += 1
        unstable = max(h) - min(h)
        times += 1
    else:
        break
print(unstable, times)
for x, y in operation:
    print(x+1,y+1)

发表于 2020-03-15 12:36:21 回复(0)
A_ = [list(i) for i in zip (A,range(1,len(A)+1))]

先对A_从大到小排一次序

sorted_A =sorted(A_,  reverse = True)

count = 0
move_record = []

缓存搬移的记录

while sorted_A[0][0]-1 >= sorted_A[-1][0]+1 and count+1 <= k:
max_index = sorted_A[0][1]
min_index = sorted_A[-1][1]
sorted_A[0][0] -=1
# 从最多堆搬走一个
sorted_A[-1][0] +=1  # 往最少堆搬来一个
count +=1
move_record.append([max_index, min_index])
sorted_A = sorted(sorted_A, reverse = True)
s = sorted_A[0][0]-sorted_A[-1][0]     # s:最小的不稳定值,即最小的差

输出结果

print('{} {}'.format(s,count))
for i in move_record:
print('{} {}'.format(i[0],i[1]))

如果不需要输出下面的m行结果的话,直接使用sort函数,判断输出的次数以及最后一次的搬运之后的max-min。

如果还想使用sort函数,可以使用zip(高度,序号),这样高度可变,输出序号数据。

编辑于 2020-02-11 20:37:34 回复(0)
def tower():
    t,m = list(map(int,input().split()))
    n = list(map(int,input().split()))
    res = []
    if max(n) - min(n) == 1:
        print('1 0')
        return
    if m == 0:
        print(str(max(n) - min(n))+' ' + str(m))
        return
    k = 0
    while max(n) - min(n) != 1 and k < m:
        max_t = n.index(max(n))
        min_t = n.index(min(n))
        res.append([max_t+1,min_t+1])
        n[n.index(max(n))] = n[n.index(max(n))] - 1
        n[n.index(min(n))] = n[n.index(min(n))] + 1
        k += 1
    print(str(max(n) - min(n)) + ' ' + str(m))
    for i in range(len(res)):
        print(str(res[i][0]) +' '+str(res[i][1]))
tower()

编辑于 2020-01-09 14:39:18 回复(0)
思路:依次从最高塔移动一块至最低塔,记录操作的塔号,直到最大差不大于1或者操作次数达到k。
!!另外要注意测试用例存在k=0的情况,一开始没想到这点一直报错。。。
n,k = map(int,input().split())
a = list(map(int,input().split()))
tout = []
tin = []
a1 = sorted(a)
if k == 0:
    print(a1[-1] - a1[0],0)
else:
    t = 1
    while t <= k:
        t1,t2=a.index(a1[-1]),a.index(a1[0])
        tout.append(t1+1)
        tin.append(t2+1)
        a[t1],a[t2] = a[t1]-1,a[t2]+1
        a1[-1],a1[0] = a1[-1]-1,a1[0]+1
        a1.sort()
        x = a1[-1] - a1[0]
        if x <= 1:
            break
        if t == k:
            break
        t += 1
    print(x,t)
    for i in range(t):
        print(tout[i],tin[i])

发表于 2019-08-23 15:34:52 回复(0)
import sys
n,k=list(map(int,sys.stdin.readline().split()))
height=list(map(int,sys.stdin.readline().split()))
res=[]
for i in range(k):
    res.append([height.index(max(height))+1,height.index(min(height))+1])
    height[height.index(max(height))]-=1
    height[height.index(min(height))]+=1
print(str(max(height)-min(height))+' '+str(k))
for i in res:
    print(str(i[0])+' '+str(i[1]))

发表于 2019-08-19 14:14:01 回复(0)
def func():
#     n,k = list(map(int, input().split()))
#     height = list(map(int, input().split()))
    
    n,k = 4,3
    height = [5, 8, 5, 4]
    
    res_list = []
    for i in range(k):
        min_index = height.index(min(height)) 
        max_index = height.index(max(height))
        
        if max(height) - min(height) >= 2:
            res_list.append([max_index+1, min_index+1])
            height[min_index] += 1
            height[max_index] -= 1
        
        else:
            break
    print("{} {}".format(max(height) - min(height),  len(res_list)))
    for item in res_list:
        print("{} {}".format(item[0], item[1]))

发表于 2019-08-03 14:20:28 回复(0)
"""
每次从最高塔取下,放在最低塔上
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n, k = list(map(int, input().strip().split()))
    a = list(map(int, input().strip().split()))
    move = []
    for _ in range(k):
        p, q = a.index(max(a)), a.index((min(a)))
        s = a[p] - a[q]
        if s <= 1:
            break
        move.append([p + 1, q + 1])
        a[p] -= 1
        a[q] += 1
    s = max(a) - min(a)
    m = len(move)
    print(s, m)
    for p, q in move:
        print(p, q)

发表于 2019-07-03 18:04:23 回复(0)