Source Code

Problem: 1153  User: yzhw 
Memory: 1220K  Time: 438MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
using namespace std;
# include <algorithm>
# include <cstdio>
# include <vector>
# include <cstring>

vector<int> data;
inline int dis(int a,int b)
{
     return min(max(a,b)-min(a,b),min(a,b)-max(a,b)+10000000);
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int num,t;
    scanf("%d",&num);
    for(int i=1;i<=num;i++)
    {
       scanf("%d",&t);
       data.push_back(t);
      
    }
    sort(data.begin(),data.end());
    long long total=0,res=0;
    /*
    cout<<endl<<endl;
    for(int i=0;i<data.size();i++)
      cout<<data[i]<<" ";
    cout<<endl;
    */
    for(int i=0;i<data.size();i++)
    {
       if(i==0)
       {
         total=0;
         for(int j=0;j<data.size();j++)
            total+=dis(data[i],data[j]);
         res=total;
       }
       else
       {
         
         //
        // cout<<"i="<<i<<endl;
         //
         
           int low1=(data[i]+5000000>10000000?data[i]-5000000:data[i]+5000000),high1=data[i-1];
           int low2=data[i],high2=(data[i-1]+5000000>10000000?data[i-1]-5000000:data[i-1]+5000000);
           long long num1,num2;
           //
         //  cout<<"low1="<<low1<<",high1="<<high1<<endl<<"low2="<<low2<<",high2="<<high2<<endl;
           //
           
           
           if(low1<=high1)
              num1=upper_bound(data.begin(),data.end(),high1)-lower_bound(data.begin(),data.end(),low1);
           else
              num1=data.end()-lower_bound(data.begin(),data.end(),low1)+upper_bound(data.begin(),data.end(),high1)-data.begin();
           //
           //cout<<data.end()-lower_bound(data.begin(),data.end(),low1)<<endl; 
           //cout<<upper_bound(data.begin(),data.end(),high1)-data.begin()<<endl;
         //system("pause");        
           //
           if(low2<=high2)
              num2=upper_bound(data.begin(),data.end(),high2)-lower_bound(data.begin(),data.end(),low2);
           else
              num2=data.end()-lower_bound(data.begin(),data.end(),low2)+upper_bound(data.begin(),data.end(),high2)-data.begin();
         //  cout<<"num1="<<num1<<",num2="<<num2<<endl;
           vector<int>::iterator up=lower_bound(data.begin(),data.end(),low2);
           if(high1<=low2)
             for(vector<int>::iterator it=upper_bound(data.begin(),data.end(),high1);it<up;it++)
                total+=dis(low2,*it)-dis(high1,*it);
           else
           {
               for(vector<int>::iterator it=upper_bound(data.begin(),data.end(),high1);it<data.end();it++)
                       total+=dis(low2,*it)-dis(high1,*it);
               for(vector<int>::iterator it=data.begin();it<up;it++)
                       total+=dis(low2,*it)-dis(high1,*it);
           }
          // cout<<"range1="<<*upper_bound(data.begin(),data.end(),high1)<<","<<*up<<endl;
           
           up=lower_bound(data.begin(),data.end(),low1);
           if(high2<=low1)
           for(vector<int>::iterator it=upper_bound(data.begin(),data.end(),high2);it<up;it++)
             total+=dis(low2,*it)-dis(high1,*it);
           else
           {
               for(vector<int>::iterator it=upper_bound(data.begin(),data.end(),high2);it<data.end();it++)
                       total+=dis(low2,*it)-dis(high1,*it);
               for(vector<int>::iterator it=data.begin();it<up;it++)
                       total+=dis(low2,*it)-dis(high1,*it);
           }
           total+=(long long)((long long)(num1-num2))*(data[i]-data[i-1]);
         //  cout<<"range2="<<*upper_bound(data.begin(),data.end(),high2)<<","<<*up<<endl;
         /*  
           
           long long testnum=0;
           for(int j=0;j<data.size();j++)
              testnum+=dis(data[j],data[i]);
           if(testnum!=total)
           {
               cout<<"i="<<i<<endl;
               cout<<"correct:"<<testnum<<endl<<"wrong:"<<total<<endl;
           }*/
          // cout<<endl<<endl;            
           res=(total<res?total:res);
       }
    }
    printf("%I64d\n",res);
    //system("pause");
    return 0;
}