1000ms

Difficulty: 4

所属公司 : 美团

时间 :2024年4月6日

算法与标签>思维

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

题解

对记录 $U$ 和 $V$ 中的元素分别进行排序，因为原始的前序累加和序列是严格递增的，打乱后排序即可还原删除后的正确顺序。
通过排序后前缀和的差分，还原出 $U$ 和 $V$ 各自对应的删除元素后剩余的原始数列，分别记为 $P_U$ 和 $P_V$ 。
遍历 $P_V$ ，找到第一个不存在于 $P_U$ 中的数 $x$ ，设其下标为 $i$ ：

如果 $i = n-1$ ，说明 $x$ 是原数列的最后一个数，直接将 $x$ 添加到 $P_U$ 末尾即可。

题目内容

小华有一组由 $n$ 个互不相等的正整数构成的数列 $P$ ，但在一次整理中不慎将其遗失。幸运的是，他留下了两份残缺的记录：

记录 $U$ 是删除数列 $P$ 中某一个元素后，对剩余元素依次求前序累加和（即每一项都是原数列从第一项到当前位置之和），并将得到的所有累加和打乱顺序后的结果。
记录 $V$ 是删除数列 $P$ 中另一个不同的元素后，用同样的方法得到的前序累加和且打乱顺序后的结果。

保证两次删除的元素位置不同。请你根据这两份记录复原出原始的数列 $P$ 。