题面

其中 \(1 \leq n \leq 2 \times 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\n" , ans);

}

巴特西

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

题面

分析

\(Code\)

最新文章

热门文章