二十道选择两道算法题。
选择就不说了，硬件方面目前了解较少。
两道算法题都过了，第一题很简单没有什么好讲的。
第二题看着题目以为会很复杂，没想到一遍过。
小美有一个由 n 个互不相等的正整数构成的数组 a，但她一不小心把 a 弄丢了，他想要重新找到 a。
好在她并不是一无所有，她还记得以下有关 a 的信息：
1. 他完全记得数组 b 的样子，并且 b 是数组 a 删除了某个 a_i 后，剩余的部分做前缀和并打乱的结果。
2. 他完全记得数组 c 的样子，并且 c 是数组 a 删除了某个 a_j 后，剩余的部分做前缀和并打乱的结果。
（保证两次删除的 a_i 和 a_j 不是同一个 a 中的元素）。
请你帮她还原出 a 数组吧。
补充：前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。
输入描述
输入包含三行。
第一行一个正整数 n\ (3 \leq n \leq 10 ^ 5)，表示数组 a 的长度。
第二行 n - 1 个正整数 b_i\ (1 \leq b_i \leq 10 ^ {14})，表示题中所述数组 b。
第二行 n - 1 个正整数 c_i\ (1 \leq c_i \leq 10 ^ {14})，表示题中所述数组 c。
（输入保证有唯一解）
输出描述
输出一行 n 个整数，表示你还原出的 a 数组。
4
8 18 14
15 9 1
输出
1 8 6 4
说明
b 数组是 a 中删除了 a[1] 后，求前缀和，再打乱得到的。
c 数组是 a 中删除了 a[4] 后，求前缀和，再打乱得到的。
思路：所谓前缀和，一定是递增的，所以题目中把打乱了完全没有用，通过排序就可以找回打乱前的数组。然后从后往前用当前前缀和减去前一个前缀和即可得到当前数字。两次操作后我们就得到了b和c的原始数组，即删除了一个a中数字的数组。
注意：此时的b，c数组和a的顺序完全一样，只是删除了一个数字。利用这一点我们才可以按照正确的顺序求出a数组。
接下来只需要找到被删除的那个数字并且插入原来数组即可。
接下来使用两个指针指向b，c，如果指针值相等则判断下一个，如果不等则说明在当前位置b，c中有一个删除了a中的一个数字。在删除的数组中，当前指针所指的数据必然为另一个数组中下一个数据（关于这点下面详细解释），将另一个数组中的数据插入删除的数组即可。举个例子1,2,3,4,5，删除2、4，自己想一想就知道了。
关于上面的解释：题目说保证有唯一解，所以删除的两个数字必然不可能连续，如果连续，则我们不可能知道这两个数字在原数组中的顺序，不知道谁先谁后。所以如果发现当前数组中被删了一个数字，那么下一个一定没有被删，两数组中一定都有该数字，只需要通过一个判断与下一个数字比较看哪个数组被删除了即可。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<long long>a(n), b(n - 1), c(n - 1);
for (int i = 0; i < n - 1; i++)
{
cin >> b[i];
}
for (int i = 0; i < n - 1; i++)
{
cin >> c[i];
}
sort(b.begin(), b.end());
sort(c.begin(), c.end());
for (int i = n - 2; i >= 1; i--)
{
b[i] = b[i] - b[i - 1];
c[i] = c[i] - c[i - 1];
}
int pb = 0, pc = 0;
while (pb < n - 1 && pc < n - 1)
{
if (b[pb] == c[pc])
{
pb++;
pc++;
continue;
}
if (b[pb + 1] == c[pc])
{
c.insert(c.begin() + pc, b[pb]);
break;
}
else if (c[pc + 1] == b[pb])
{
b.insert(b.begin() + pc, c[pc]);
break;
}
else
{
}
}
if (b.size() == n)
{
for (int i = 0; i < n; i++)
{
cout << b[i] << ' ';
}
}
else if (c.size() == 0)
{
for (int i = 0; i < n; i++)
{
cout << c[i] << ' ';
}
}
else
{
}
}
