首页 > 试题广场 >

牛牛的消消乐

[编程题]牛牛的消消乐
  • 热度指数：18872 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个数组 nums，其中有 n 个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。
每次操作形如：任选一个整数 x ，将数组中所有大于等于 x 的数减去 x 。
示例1

输入

[2,1,3]

输出

0

说明

初始数组为 [2, 1, 3]。
先选择 x = 2，则所有大于等于 2 的元素减去 2 ，变成 [0, 1, 1]。
再选择 x = 1，则所有大于等于 1 的元素减去 1 ，变成 [0, 0, 0]。
所以数组元素之和的最小值为 0。

备注:
对于所有的测试数据，保证有 且  。
算法知识视频讲解
开通博客
头像 飛魚&鳥
发表于 2020-03-29 19:19:03
首先问题可以简化为，选择两个高度和，并且有，对于每个元素，如果那么该高度最终会被减去，如果该高度会被减去，同理如果该高度会被减去。 我们将数组从小到大排序，并画出删除区域，我们可以将消去的面积分为三部分计算，一部分是以为高，一部分是以为高，第三部分是以为高。并且我们可以推算得到，三个高度至少有两个高 展开全文
去ta的博客 赞 (13) 回复(7) 收起
头像 摸鱼学大师
发表于 2021-07-29 13:51:23
思路： 题目的主要信息： 对一个数组，每次选1个元素进行操作，两次操作后使数组和最小 操作为：任选一个元素x，将数组中所有大于等于x的数减去x 方法一：暴力法具体做法：首先对数组进行排序，使之成为递增顺序。求一个数组的和sum，然后就是找到sum要减去的最大值。这个最大值就是进行两次操作的时候 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 坑王之王
发表于 2021-10-28 10:29:50
思路： 用两层循环找到数据处理的最小值。第一层循环，数组依次以每个元素作为减数，以第i个元素作为被减数，相减后生成新的数组。 第二层循环以第一层循环生成的新的数组，重复第一层循环的操作，然后将最后的元素结果相加之和。遍历后比较得到相加之和的最小值。 import java 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 _mew_
发表于 2021-03-06 20:45:46
class Solution: def minimumValueAfterDispel(self, nums): """ NC501 牛牛的消消乐 给定一个数组 nums，其中有 n 个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛一霸
发表于 2021-08-14 22:47:57
题目：牛牛的消消乐描述：给定一个数组 nums，其中有n个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。每次操作形如：任选一个整数x ，将数组中所有大于等于x的数减去x。示例1：输入：[2,1,3]，返回值：0说明：初始数组为 [2, 1, 3]。先选择 x = 2，则所有大于等于 2 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 泪无声呢
发表于 2021-07-28 17:53:19
牛牛的消消乐 问题描述：给定一个数组 nums，其中有 n 个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。每次操作形如：任选一个整数 x ，将数组中所有大于等于 x 的数减去 x 。 示例 输入：[2,1,3] 返回值：0 说明：初始数组为 [2, 1, 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-07-30 16:12:29
题目描述给定一个数组 nums，其中有 n 个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。每次操作形如：任选一个整数 x ，将数组中所有大于等于 x 的数减去 x 。 方法一：暴力方法 求解思路对于题目给出的操作规则，我们首先对数组进行排序，使其按照递增的顺序排列。题目要求的数组和，即 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 电玩码子
发表于 2022-02-11 22:34:46
JAVA暴力解题法，通过多重for循环外加最小值替换获取到最终要返回的值。这里不再赘述。 这里有一个注意事项，就是按照直接全量for循环的最终代码运行没有问题，但是性能无法满足题目要求。 所以在for循环处理的时候注意先对数组排序，排序后，大小判断就省略的，同时在循环时不是每一个循环都是从0到结尾。 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数组 基础数学
难度：
33条回答 13674浏览

热门推荐

通过挑战的用户

查看代码

相关试题

牛牛的消消乐

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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