蓝桥杯-修改数组（python）

一、题目

题目 2301: 蓝桥杯2019年第十届省赛真题-修改数组
时间限制: 1Sec 内存限制: 128MB 提交: 5051 解决: 1223
题目描述
给定一个长度为 N 的数组 A = [A1, A2, · · · AN ]，数组中有可能有重复出现 的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。

小明会依次修改 A2,A3,··· ,AN。

当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。

如果出现过，则 小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。

当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。

现在给定初始的 A 数组，请你计算出最终的 A 数组

输入

第一行包含一个整数 N。

第二行包含N个整数A1,A2,··· ,AN

对于 80% 的评测用例，1 ≤ N ≤ 10000。

对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。

输出
输出N个整数，依次是最终的A1,A2,··· ,AN。

样例输入

5
2 1 1 3 4

样例输出

2 1 3 4 5

二、思路和代码

思路：这道题解的本质其实是动态规划。

has数组中has[i]的含义是：目前为止，i到比它大的未出现过的数的距离。

然后每次加入一个数字，更新一次has数组。

has数组的更新规则是，将经过的所有数从后往前更新，假设先经过a后经过b，则更新b后，a的更新规则为：has[a] += has[b]。

总结：这道题本身是没有最优子结构的，但将问题转化为求一个数到比它大的最小未使用过的数，就有了最优子结构。

因为这道题是求一个数到比它大的最小未使用过的数，所以依赖关系应该是前面的数据依赖后面的数据，故每次通过栈从后往前更新。

代码：

n = int(input())
ls = [int(x) for x in input().split()]

# i到比它大的最近的未使用数字的距离
has = [0 for _ in range(1000000)]
# 用栈记录每次求解经过的数
stack = list()
# 逐个求解
for i in range(n):
    # 若出现过，则用has[ls[i]]更新ls[i]，每次经过一个数，将该数压入栈
    while has[ls[i]] >= 1:
        stack.append(ls[i])
        ls[i] += has[ls[i]]
    # 通过栈更新has数组中被经过的数
    has[ls[i]] += 1
    last = ls[i]
    while len(stack) != 0:
        x = stack.pop()
        has[x] += has[last]
        last = x

print(" ".join([str(x) for x in ls]))