首页 > 试题广场 >

塔

[编程题]塔
  • 热度指数：20286 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小易有一些立方体，每个立方体的边长为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座塔上。
示例1

输入

3 2
5 8 5

输出

0 2
2 1
2 3
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 14:38:02
精华题解 题目难度：二星考察点：贪心、模拟 方法：贪心、模拟 分析：我们分析一下题意，如果想尽可能的让塔的不稳定性小的话，那么就需要让最高塔高度与最低塔高度的差尽可能低，也就是让最高塔的高度尽可能低，最低塔的高度尽可能高。那么我们每次进行操作的时候就是首先将整个高度数组按照从小到大进行排序，然后高度最大值- 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客781393260号
发表于 2021-03-25 11:58:44
一开始想用优先队列，但维护最大堆最小堆太麻烦，转而想到用一个set来做，该set的begin()就是当前最低的塔该set的rbegin()就是当前最高的塔用erase对选中的元素出队，ran'd #include<iostream> #include<vector> #inc 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 c小白进击之路
发表于 2021-04-13 16:02:34
最简单逻辑求解 每走一步，最高-1，最矮+1，k步之后的数组是结果。 -------------------------------------------------------------------------------------------- #include& 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 laglangyue
发表于 2020-05-19 20:52:38
面向对象编程：堆java提供了优先级队列PriorityQueue，底层是堆实现的，建立每一个塔对象，用两个优先级队列包含所有塔，一个大根堆，一个小根堆。然后就简单了，从大小根堆取出对象，执行对象的add,remove方法，然后把操作日志记录到arraylist中去。该思路帮助回忆了一手堆和优先级队 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 PHP工程师 排序 贪心 模拟 网易 2019 Java工程师
来自：网易2019秋季校园招...
上传者：小小
难度：
103条回答 18375浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号