考试时没审清题，内存超限.......
事实上这是个三分题，
因为我们先假设一个最高点和最高点的高度，随着最高点高度的增加，
其他点的贡献为abs(a[j]-(h[i]-abs（i-j）))(j为最高点)
所以点的贡献的和是一个单峰函数（下凹的）
那么我们三分即可
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<string> 7 #include<map> 8 #include<vector> 9 #include<queue> 10 #include<set> 11 #define MAXN 200010 12 #define ps push_back 13 #define int long long 14 using namespace std; 15 int n;int a[MAXN];int max_r=0;int l,r;int minn=0x7ffffffffffff; 16 int work(int x,int root) 17 { 18 int sum=0; 19 for(int i=1;i<=n;++i) 20 { 21 int me=x-abs(i-root); 22 sum+=abs(a[i]-me); 23 } 24 minn=min(minn,sum); 25 return sum; 26 } 27 void three_divide(int x) 28 { 29 l=max(x,n-x+1);r=0x7ffffffffffff;;int mid; 30 while(l+2<r) 31 { 32 mid=l+(r-l)/3;int midd=r-(r-l)/3; 33 if(work(mid,x)>work(midd,x)) 34 { 35 l=mid; 36 } 37 else 38 r=midd; 39 //printf("l=%lld mid=%lld r=%lld ",l,mid,r); 40 } 41 for(int i=l;i<=r;++i) 42 minn=min(minn,work(i,x)); 43 } 44 signed main() 45 { 46 scanf("%lld",&n); 47 for(int i=1;i<=n;++i) 48 { 49 scanf("%lld",&a[i]); 50 max_r=max(max_r,a[i]); 51 } 52 53 for(int i=1;i<=n;++i) 54 { 55 three_divide(i); 56 } 57 printf("%lld ",minn); 58 }
至于正解
再次%%%%%skyh（用不是正解的方法碾压正解）
第一次听说模拟退火，很神奇的随机化算法（以后骗分的好技巧2333333），
然后就学了学，
定义了几个量
T初始化温度，esp最终温度，base变化倍数
nowpos，nowans现在位置和答案，lastpos，lastans
然后每次通过上一次位置随机化这一次的位置
之后改变ans时一种是lastans更优另一种是
(exp((lastans-nowans)/T)*RAND_MAX)>rand())
一种我不太会证的定理......总之就是以一定的概率即使不优也要转移
然后丑陋的代码
1 #include<bits/stdc++.h> 2 #define MAXN 100010 3 #define ps push_back 4 #define int long long 5 using namespace std; 6 double esp=1e-5,T=1000,base=0.975; 7 int nowans,lastans; 8 int nowpos,lastpos; 9 int s[MAXN];int a[MAXN]; 10 int n; 11 int ans=0x7fffffffffff; 12 int find(int x) 13 { 14 int mid=(1+n)>>1; 15 for(int i=1;i<=n;++i)s[i]=a[i]+abs(x-i); 16 nth_element(s+1,s+mid,s+n+1); 17 int cal=s[mid]; 18 cal=max(cal,max(x,n-x+1)); 19 int tot=0; 20 for(int i=1;i<=n;++i)tot+=abs(cal-s[i]); 21 return tot; 22 } 23 signed main() 24 { 25 srand(time(0)); 26 scanf("%lld",&n); 27 for(int i=1;i<=n;++i) 28 { 29 scanf("%lld",&a[i]); 30 } 31 lastpos=(n+1)/2; 32 lastans=find(lastpos); 33 ans=min(ans,lastans); 34 while(T>esp) 35 { 36 nowpos=lastpos+(2ll*rand()-RAND_MAX)*T*0.000001; 37 if(nowpos<1) 38 { 39 nowpos=max(1ll,nowpos); 40 nowpos=min(n,nowpos); 41 } 42 else 43 { 44 nowpos=(nowpos%n+n-1)%n+1; 45 } 46 nowans=find(nowpos); 47 if(nowans<lastans||(exp((lastans-nowans)/T)*RAND_MAX)>rand()) 48 { 49 lastans=nowans; 50 lastpos=nowpos; 51 } 52 ans=min(ans,nowans); 53 T*=base; 54 } 55 printf("%lld ",ans); 56 }