首页 > 试题广场 >

mex

[编程题]mex

热度指数：1704 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给你一个由 $n$ 个自然数（非负整数）组成的数组 $\{a_1,a_2,\dots,a_n\}$ ，我们定义一轮操作：
$\hspace{23pt}\bullet\,$ 计算出当前数组的 $\operatorname{mex}$ ，随后，使得所有的 $a_i := \max\{0,a_i - \operatorname{mex}\}$ 。换句话说，对于任意的 $1\leqq i\leqq n$ ，使得 $a_i\gets \max \{0,a_i - \operatorname{mex}\}$ 。
$\hspace{15pt}$ 小牛想知道你至少需要执行多少轮（也可以不执行）操作，才能使得数组 $a$ 中的每个数都相同？如果无法使得数组 $a$ 中的每个数都相同，则直接输出 $-1$ 。

$\hspace{15pt}$ 整数数组的 $\operatorname{mex}$ 定义为没有出现在数组中的最小非负整数。例如 $\operatorname{mex} \{1,2,3 \} =0$ 、 $\operatorname{mex} \{0,2,5\} =1$ 。

输入描述:

第一行输入一个整数  代表数组中的元素数量。 
第二行输入  个整数  代表数组中的元素。

输出描述:

如果无法使得数组  中的每个数都相同，则直接输出 ；否则，输出一个整数，代表至少需要执行的轮数。

示例1

输入

6
0 1 2 3 4 5

输出

说明

在这个样例中，第一轮数组的  为 ，所以：
对于第一个元素 ，使用  替换；
对于第二个元素 ，使用  替换；
对于第三个元素 ，使用  替换；
对于第四个元素 ，使用  替换；
对于第五个元素 ，使用  替换；
对于第六个元素 ，使用  替换。
得到数组 ，满足题干条件。所以，至少需要执行  轮操作。

示例2

输入

5
3 1 2 4 5

输出

-1

说明

在这个样例中，由于第一轮数组的  为 ，所以无论执行多少次操作，数组都不会改变，所以无法使所有数变为相同值。

示例3

输入

6
0 1 3 4 7 9

输出

说明

在这个样例中：
第一轮操作：，操作完后数组变为 ； 
第二轮操作：，操作完后数组变为 ；
第三轮操作：，操作完后数组变为 ； 
第四轮操作：，操作完后数组变为 ； 
第五轮操作：，操作完后数组变为 。
综上所述，至少需要执行  轮操作。

算法知识视频讲解

丨阿伟丨

发表于 2025-08-28 14:10:13

题目链接小红的01串题目描述给定一个由个非负整数组成的数组。一轮操作定义为：首先计算数组的（未在数组中出现的最小非负整数），然后将数组中的每个数更新为。求至少需要多少轮操作才能使数组中的每个数都相同。如果不可能，则输出 -1。解题思路本题要求计算最少需要多少轮操作才能使数组中的展开全文

立花泷之介

发表于 2026-02-27 14:46:12

这道题目是一道典型的博弈/构造类贪心题，核心在于理解 mex（最小未出现的非负整数）对数组变化的实质影响。核心思路分析我们需要通过操作 ai = max(0, ai - mex)让数组中所有元素相等。情况 A：数组元素已经全部相同此时不需要任何操作，直接输出 0。情况 B：数组元素不全相同，且数组中展开全文

Night_crusing

发表于 2026-03-07 00:43:31

很有意思的一个题，想要高效的完成这个题目我们可以关注每一次操作的本质，对于比较特殊的例如 1 2 3 4 5 这种没有0的mex为0,不管多少次操作都是无效的 0 0 0 0 0 这种不需要操作就可以分析完了特殊的我们可以来看比较一般的情况，例如 0 2026 由于数组有0才能有有效的mex本展开全文

BraveCoder

发表于 2025-09-21 15:04:38

import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n 展开全文

rpcwx

发表于 2026-02-17 21:13:52

#include <iostream> using namespace std; #include<set> #include<algorithm> int main(){ set<long long>a; int n; ci 展开全文

小海胆胆

发表于 2026-03-10 16:40:44

mex 思路这道题乍一看像是模拟题——每轮算个 MEX，然后所有元素减掉它，直到全部相等。但直接模拟肯定超时，因为操作轮数可以达到级别。关键在于找到规律，跳过大量重复操作。什么时候无解？如果数组里没有 0，那 MEX = 0，减 0 等于啥都没变。除非数组本身已经全部相等（直接输出 0），展开全文

ZYCwuque

发表于 2026-03-09 17:15:36

这题是思维题，需要自己去发现规律经过研究发现，对于排好序后的{0,p1,p2,p3}需要p3-(k-1)次，这是一般规律除此之外，我们还需特判两种情况，一种是原数组原本就是每个数都相同的还有一种就是原数组中没有0，mex只能取0，使得永远无法变化成相同的 import java.util.Arr 展开全文

冷艳的西红柿刷牛客

发表于 2025-10-06 20:48:00

import java.util.Arrays; import java.util.Objects; import java.util.Random; import java.util.Scanner; /** * @author supermejane * @date 2025/10/6 展开全文

问题信息

难度：

2条回答 23收藏 302浏览

mex

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题