2019网易秋招笔试编程题：塔

╰+哭是因爲堅強的太久メ 2022-05-16 04:18 277阅读 0赞

题目链接：[https://www.nowcoder.com/questionTerminal/54868056c5664586b121d9098d008719][https_www.nowcoder.com_questionTerminal_54868056c5664586b121d9098d008719]  
来源：牛客网

--------------------

# 题目 #

小易有一些立方体，每个立方体的边长为1，他用这些立方体搭了一些塔。  
现在小易定义：这些塔的不稳定值为它们之中最高的塔与最低的塔的高度差。  
小易想让这些塔尽量稳定，所以他进行了如下操作：每次从某座塔上取下一块立方体，并把它放到另一座塔上。  
注意，小易不会把立方体放到它原本的那座塔上，因为他认为这样毫无意义。  
现在小易想要知道，他进行了不超过k次操作之后，不稳定值最小是多少。

### 输入描述 ###

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

### 输出描述 ###

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

### 示例 ###

**输入**

3 2
    5 8 5

**输出**

0 2
    2 1
    2 3

--------------------

# 思路和代码 #

# -*- coding: utf-8 -*-
    '''
    思路： 其实很简单，每次排个序，然后从最大堆往最小堆搬一个即可，
         并记录堆序号，直到最大堆-最小堆<1 或者 移动次数达到k。
         这里排序并保留堆序号的方法，是用的python内置的sort()函数，
         当然也可以调用 numpy的argsort()。
    '''
    
    # 为后面排序定义一个方法
    def by_value(t):
        return t[1]
    
    # 读入数据
    n,k = list(map(int, input().split()))
    A = list(map(int, input().split())) # A = [a1,a2,a3,...an]
    #n,k = [3,2]
    #A = [5,8,5]
    
    # A_ = [[1, 5], [2, 8], [3, 5]] 其中每个元素表示：[第i堆，对应塔数]
    A_ = [list(i) for i in zip(range(1,len(A)+1),A)]
    
    # 先对A_从大到小排一次序
    sorted_A = sorted(A_,key = by_value,reverse=True)
    count = 0
    move_record = [] # 缓存搬移的记录
    
    while sorted_A[0][1]-1 >= sorted_A[-1][1]+1 and count+1<=k:
    
        max_index = sorted_A[0][0]
        min_index = sorted_A[-1][0]
    
        sorted_A[0][1] -= 1 # 从最多堆搬走一个
        sorted_A[-1][1] += 1 # 往最少堆搬来一个
        count += 1
        move_record.append([max_index,min_index])
    
        sorted_A = sorted(sorted_A,key = by_value,reverse=True)
    
    # 打印结果
    s = sorted_A[0][1]-sorted_A[-1][1] # s:最小的不稳定值，即最小的差
    print('{} {}'.format(s,count))
    for i in move_record:
        print('{} {}'.format(i[0],i[1]))

运行时间：50 ms  
占用内存：3684K  
牛客网

--------------------

[https_www.nowcoder.com_questionTerminal_54868056c5664586b121d9098d008719]: https://www.nowcoder.com/questionTerminal/54868056c5664586b121d9098d008719