类似于暴力,借鉴了某个大佬的思路,同时给出了更详细的注释, 原思路来源。
#include<bits/stdc++.h>
using namespace std;
const int j=2000000;
int n,ans;
int v[4000005];//在拓展最小值或最大值时,往两边拓展最多会再多拓展1倍空间,同时又会有正负,所以要4倍空间。该数组用于记录某个值是否出现。
int main(){
int n;
cin>>n;
int x,y;//前两个值特殊统计(其实第二个值可以用这种方法找到最小波动,但比较慢)。
cin>>x>>y;
ans=abs(x-y)+x;//初始化。
n-=2;
v[x+j]=1;
v[y+j]=1;//打标记。
for(int i=0,x;i<n;i++){
cin>>x;
int t=0;//表示当前查找到的数与今日营业额差t。
while(1){
if(v[x+j+t]==1||v[x+j-t]==1){
ans+=t;//第一个访问到有标记的,一定是最小波动值。
break;
}
t++;
}
v[x+j]=1;//打标记。
}
cout<<ans;
return 0;
}