前言
题目
- 原题地址：E. MEX and Increments
- 题目编号：1619E
- 目标算法：dp（动态规划）
- 难度评分：1700
1.题目大意
- 给你一个由n个非负数构成的数组
- 定义MEX为数组中不存在的最小非负数，例如：
- [3, 1, 0] MEX = 2
- [3, 3, 1, 4] MEX = 0
- 要求使MEX = 0到n需要对数组进行最小的操作次数，无法实现输出-1
- （一次操作就是对数组中任意元素+1）
2.题目分析
- 首先有几个注意要点
- 当前i对应的MEX不满足题意为-1时，后面大于i的数对应的MEX均为-1
- 当前i对应的MEX满足题意时，前面必然可以构造出一个小序列，满足0到i的元素有且只有一个。
- 构造小序列的最新一位i-1时，要从已构造元素的重复元素中选出最接近i-1的一个进行构造。
- 根据要点2以及题目要求，我们可以得到以下公式：
ans = dp + cnt- 其中：
- ans：要求的最小操作数
- dp：构造小序列所需的最小操作数
- cnt：当前数值元素的个数
- 根据要点3，进一步添加2个优先队列：
- up：升序，用于存储样例中的所有元素
- down：降序，用于存储小于当前i的重复元素
- 以样例中的0 1 2 3 4 3 2为例进行演示
| MEX |
up |
down |
dp |
cnt |
ans |
| 0 |
0 1 2 2 3 3 4 |
? |
0 |
1 |
0 + 1 = 1 |
| 1 |
1 2 2 3 3 4 |
0 |
1 - 1 - 0 + 0 = 0 |
1 |
0 + 1 = 1 |
| 2 |
2 2 3 3 4 |
1 |
2 - 1 - 1 + 0 = 0 |
1 |
0 + 1 = 1 |
| 3 |
3 3 4 |
2 2 |
3 - 1 - 2 + 0 = 0 |
2 |
0 + 2 = 2 |
| 4 |
4 |
3 3 2 |
4 - 1 - 3 + 0 = 0 |
2 |
0 + 2 = 2 |
| 5 |
? |
4 3 2 |
5 - 1 - 4 + 0 = 0 |
0 |
0 + 0 = 0 |
| 6 |
? |
3 2 |
6 - 1 - 3 + 0 = 2 |
0 |
2 + 0 = 2 |
| 7 |
? |
2 |
7 - 1 - 2 + 2 = 6 |
0 |
6 + 0 = 6 |
3.题目代码
#include
#include
#include
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n;
int tmp;
cin >>n;
long long cnt[200005]={0};//有可能有大于n的数,所以数组要开到最大
priority_queue,greater> up;//升序
priority_queue,less> down;//降序
for(int i=0;i> tmp;
cnt[tmp]++;
up.push(tmp);
}
long long dp = 0;//创造小序列的操作数
long long ans = 0;
cout << cnt[0] << " ";
for(int i=1;i<=n;i++)
{
while(!up.empty()&&up.top()
- ps：在做题的过程中发现对于0的特判可以直接包含进去，于是以上代码就是最后的版本