題面

分析

此題真是一言難盡。下面這么大一串，真的只是在講一個小模擬。。。此題也是被幾個julao反復講，各種五花八門的奇淫巧技，什么數學變形，樹狀數組，差分，單調……好吧，我是那種只會30分暴力的人，也沒理由嫌棄這些我聽不懂的做法。

于是看到了一篇極其妙的題解，思路是建坐標系，然而這位julao的題解的code跑出來只有30pts。借用大佬的圖
首先，以i為橫坐標，ai為縱坐標，建立平面直角坐標系，將點全部描在坐標系里，并畫出y=x的直線，可以發現，點到直線的豎直距離
之和，就是我們要求的答案。

然而怎么求不同順序的答案呢？

只需要左右平移這條直線！
可以發現，向左平移，在這條直線上方的點，到直線的豎直距離會減小1，而在這條直線下方或處于直線上的點，到直線的豎直距離會?加1。

如果是向右平移，顯然是恰好相反，所以要枚舉所有情況，只需要將這條直線向一個方向，平移n次，每次平移一個單位。
然而有一個特殊的點，n->1
假如選擇向左平移，1~n-1個點的值的計算方式完全不變。
但是第n個點會變，所以每次平移特殊處理第n個點。

其實你或許已經發現了，圖象是答案的幾何含義，本質上我們的平移操作等效于在序列上移動下標。
到這里，大體思路就已經出現了，但是我覺得細節也是比較難懂的（或許是我太菜了），所以我再稍微補充一下。

1.怎么維護每次移動后的直線上下方的點呢？用up,down記錄在直線上方下方的點的個數。先預處理點對于初始直線的上下方個數。再維?護一個d[ ]數組，每出現一個處于直線上方的點，就將這個 d[s]++(s為這個點到直線的豎直距離)。這 表示在直線上方的距離處s處，有d[s]個 點，由初中數學知識易證，y=x向左平移1單位等價于向上平移1單位。所以當我們一共平移了i個單位后，我們就需要利用d[i]來更?新在直線上方的點，顯然，在直線上方的點的數量up-=d[i]，因為本來離初始直線距離為i的點，在直線經過i個單位的平移后，已經落在?了直線上，而不再在直線上方。相應地down+=d[i]

2.因為ai<=n的，所以第n個點本來一定是屬于down集的，現在相當于它移到了第一個位置，只要比1大的，就可從down集出來進入up集。
3.計算答案的時候是tmp+=down-up根據2中所述，最后一個點顯然屬于down集，所以它已經被算成了，對答案的貢獻加一，所以真正的更新方式應是tmp+=down-up-1.
溫馨提示：1.longlong
2.數組開四倍。我掛了半天，最后瞎搞胡亂改錯然后過了。01 dalao給我指點了一下，因為按照序列的理論上來說，d的偏移量是2n，而這又是個環，所以是4n空間。

?代碼

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define N 4000100 #define ll long long ll a[N],d[N]; ll n,ans,tmp,up,down; int main() {scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);if(a[i]>i)tmp+=a[i]-i,up++,d[a[i]-i]++;else tmp+=i-a[i],down++;} ans=tmp;for(int i=1;i<=n;i++){tmp+=down-up-1;tmp-=n-a[n-i+1],tmp+=a[n-i+1]-1;if(a[n-i+1]>1)up++,down--,d[i+a[n-i+1]-1]++;down+=d[i],up-=d[i];ans=min(ans,tmp); }printf("%lld\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/NSD-email0820/p/9735072.html

總結

以上是生活随笔為你收集整理的【NOIP模拟】健美猫的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。