有限自动机解法,O(N)复杂度，伪动态规划

具体思路如下：

1. 首先对于超出边界的(小于等于0，大于n)，可以直接归到边界。
2. 记录每个数字出现的个数，采用有限状态机一次遍历可以得到答案
3. 分为三个状态：初始状态，多余状态和缺少状态。设当前遍历为index，多余状态多余的数均为index-1；缺少状态缺少的数为index-1,index-2,...状态转移看代码，ans更新思路见4
4. 在多余状态下，设此前多余了pre1个数字，则在遍历下一个数时，这pre1个数都需要加1，即ans += pre1；在缺少状态下，设此前缺少了pre2个数字，则将当前index的数全拿来补全缺少的数，从小补齐，即ans += counts[index] * (2 * pre2 - counts[index] + 1) / 2;这样可以使得遍历下个数时，缺少的数仍为index-1,index-2,...

#include<iostream>
#include<vector>
#include<unordered_set>
#include<algorithm>

using namespace std;


enum State
{
	inital = 0,
	preMore = 1,
	preLess = 2,
};

int main()
{
	int n = 0;
	cin >> n;
	long ans = 0;
	
	vector<int> counts = vector<int>(n, 0);
	int a = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		if (a <= 0)
		{
			counts[0] += 1;
			ans += 1 - a;
		}
		else if (a > n)
		{
			counts[n - 1] += 1;
			ans += a - n;
		}
		else
		{
			counts[a - 1] += 1;
		}
	}

	//从头开始遍历counts，有三种状态，
	//1.inital：初始状态，此前的数个数正好等于需要有的个数
	//2.preMore：此前的数多于需要的数，多出pre1个
	//3.preLess：此前的数少于需要的数，少pre2个
	int index = 0;
	int pre1 = 0;
	int pre2 = 0;
	enum State s = State::inital;
	while (index < n)
	{
		switch (s)
		{
		case State::inital:
			//对于初始状态，若当前个数为1，则可以维持初始状态
			//若为0，则转入preLess状态，若大于1，转入preMore状态
			if (counts[index] == 0)
			{
				s = State::preLess;
				pre2 = 1;
			}
			else if (counts[index] > 1)
			{
				s = State::preMore;
				pre1 = counts[index] - 1;
			}
			break;
		case State::preMore:
			//对于preMore状态，若当前个数为0且pre1正好为1，转入初始状态
			//否则维持状态，并更新ans与pre1
			if (counts[index] == 0 && pre1 == 1)
			{
				pre1 = 0;
				ans += 1;
				s = State::inital;
			}
			else
			{
				ans += pre1;
				pre1 += counts[index] - 1;
			}
			break;
		case State::preLess:
			//对于preLess状态，若当前个数为pre2 + 1，则可以转入初始状态
			//若大于pre2 + 1,需要转入preMore状态
			//否则维持状态
			if (counts[index] == pre2 + 1)
			{
				ans += pre2 * (pre2 + 1) / 2;
				pre2 = 0;
				s = State::inital;
			}
			else if (counts[index] > pre2 + 1)
			{
				pre1 = counts[index] - pre2 - 1;
				ans += pre2 * (pre2 + 1) / 2;
				pre2 = 0;
				s = State::preMore;
			}
			else
			{
				ans += counts[index] * (2 * pre2 - counts[index] + 1) / 2;
				pre2 -= counts[index] - 1;
			}
			break;
		default:
			break;
		}
		index += 1;
	}

	cout << ans << endl;
}