【3月8日特训】经验总结_给定一个长度为 n 的数组 a=[a 1 ,a 2 , a n ],数组中有可能有重复出现的整数

一

给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求
第20190324 项的最后4 位数字。

这个题我们用数组存放会超时，所以用传统循环进行求解

#include<stdio.h>
int main() {
	int a = 1, b = 1, c = 1;
	int now;
	for (int i = 4; i <= 20190324; i++) {
		now = (a % 10000 + b % 10000 + c % 10000) % 10000;
		a = b;
		b = c;
		c = now;
	}
	printf("%d\n", now);
}
1
2
3
4
5
6
7
8
9
10
11
12

答案：4659

二

由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。
这个法术需要用到他手中的49 张法术符，上面分别写着1 至49 这49 个数字。
法术一共持续7 周，每天小明都要使用一张法术符，法术符不能重复使用。
每周，小明施展法术产生的能量为这周7 张法术符上数字的中位数。
法术施展完7 周后，求雨将获得成功，降雨量为7 周能量的中位数。
由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？
链接

三

给定一个长度为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(1<=N<=100000)
第二行包含N个整数A1,A2,…,AN(1<=Ai<=1000000)
输出
输出N个整数，依次是最终的A1,A2,…,AN
样例输入 Copy
5
2 1 1 3 4
样例输出 Copy
2 1 3 4 5
核心思想：桶排序计数+边输入边判断