JZOJ 5343. 【NOIP2017模拟9.3A组】健美猫

题面

其中 (1 leq n leq 2 imes 10^6)

分析

考虑每次移动，发现负数对答案贡献少 (1)，非负数多 (1)
每次移动都加了 (1)
负数变非负数关键点在于 (0)
把所有值映射到数轴上，每次加一相当于原点向左移一位
讨论移位后负数数量的变化即可
首位则特别处理
我们只需要记录负数的情况（见 (f)）

(Code)

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long LL;

const int N = 4e6 + 5;
int n , s1 , s2 , s[N] , f[N];
LL ans , sum;

int main()
{
	scanf("%d" , &n);
	for(register int i = 1; i <= n; i++)
	{
		scanf("%d" , &s[i]);
		if (s[i] - i < 0) f[i - s[i]]++ , s2++;
		ans += abs(s[i] - i);
	}
	s1 = n - s2 , sum = ans;
	for(register int i = 1; i < n; i++)
	{
		sum += s1 - s2 - 1 - (s[i] - 1) + abs(s[i] - n);
		s2 -= f[i] , s1 += f[i];
		if (s[i] - n < 0) ++s2 , --s1 , ++f[n - s[i] + i];
		ans = min(ans , sum);
	}
	printf("%lld
" , ans);
}