【JZOJ5343】【NOIP模拟】健美猫（模拟）

健美猫（模拟）"/>

【JZOJ5343】【NOIP模拟】健美猫（模拟）

Description

Solution

由于比较的蠢，比赛的时候没有想出来。
一开始的方向就搞错了，搞了个自以为是对的贪心，然后就一直往这个地方想，用的时间太多就弃疗了。
其实思想还是比较的简单的，首先把原序列的答案求一次，我们可以逆向考虑一下，不用把序列移动，把下标移动。
比如把每个下标向左移动一格，那么原本a[i]>i的值会减1，a[i]<=i的值会+1，还有下标从n到1的数会改变一下。
然后这个可以用数据结构来做，也可以直接模拟。

Code

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=4e6+7;
typedef long long ll;
ll i,j,k,l,t,n,m,ans,an;
ll a[maxn],bz[maxn],bb,cc;
int main(){
//  freopen("fan.in","r",stdin);scanf("%lld",&n);fo(i,1,n){scanf("%lld",&a[i]);if(a[i]>i)ans+=a[i]-i,bz[min(n-i+a[i],a[i]-i)]++,bb++;else ans+=i-a[i],cc++;}an=ans;fo(i,1,n){ans+=cc-bb;ans-=n+1-a[n-i+1];ans+=a[n-i+1]-1;cc--;if(a[n-i+1]>1)bb++,bz[i+a[n-i+1]-1]++;else cc++;bb-=bz[i],cc+=bz[i];an=min(an,ans);}printf("%lld\n",an);
}