记录编号	424140	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.160 s
提交时间	2017-07-12 20:58:14	内存使用	0.31 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f
#define ls(x) (x->son[0])
#define rs(x) (x->son[1])
#define size(x) ((x)?(x->size):0)
int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-')
            f=-1;
        ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
	    s=(s<<1)+(s<<3)+(ch^48);
	    ch=getchar();
	}
	return s*f;
}
int n,check=0;
struct node{
	int val,key,size;
	node *son[2];
	node(){
	    val=key=size=0;
	    son[0]=son[1]=NULL;
	}
	node(int x);
}*root,*null=new node();
node ::node(int x){
    val=x;
    key=rand();
    size=1;
    son[0]=son[1]=null;
}
void pushup(node *&rt){
    rt->size=size(ls(rt))+1+size(rs(rt));
}
void turn(node *& rt,int d){
    node *t=rt->son[d^1];
    rt->son[d^1]=t->son[d];
    pushup(rt);
    t->son[d]=rt;
    pushup(t);
    rt=t;
}
void insert(node *&rt,int x){
    if(rt==null){
        rt=new node(x);
        return ;
	}
	int d=rt->val>x;
	insert(rt->son[d^1],x);
	pushup(rt);
	if(rt->son[d^1]->key>rt->key)
	    turn(rt,d);
}
int ques_ord(int x){
    node *rt=root;
    int ans=0;
    while(rt!=null){
        if(x>rt->val){
            ans+=size(ls(rt))+1;
            rt=rs(rt);
		}
		else{
			rt=ls(rt);
		}
	}
	return ans;
}
int ques_pos(int k){
    node *rt=root;
    while(rt!=null){
        if(size(ls(rt))+1==k)
            return rt->val;
        if(size(ls(rt))+1>k)
            rt=ls(rt);
        else{
            k-=size(ls(rt))+1;
            rt=rs(rt);
		}
	}
	return inf;
}
int main(){
	freopen("turnover.in","r",stdin);
	freopen("turnover.out","w",stdout);
    n=read();
    root=null;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(i==1){
            ans=read();
            insert(root,ans);
		}
		else{
		    int x=read();
		    int ans1=ques_pos(ques_ord(x));
		    int ans2=ques_pos(ques_ord(x)+1);
		    ans+=min(abs(x-ans1),abs(x-ans2));
		    insert(root,x);
		}
	}
	printf("%d\n",ans);
	return 0;
}