描述
在一条数轴上有N家商店，它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行一个整数N，第二行N个整数A[1]~A[N]。
输出格式
一个整数，表示距离之和的最小值。
样例输入
4
6 2 9 1
样例输出
12
数据范围与约定
对于100%的数据: N<=100000, A[i]<=1000000
这是一道裸的中位数题，但本人不想用快排，于是用了求第k小数的做法（不完全排序）。
方法1（快排）：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,a[N],p;long long ans;
#define g getchar()
void qr(int &x)
{
char c=g;x=0;bool v=0;
while(!(('0'<=c&&c<='9')||c=='-'))c=g;
if(c=='-')v=1,c=g;
while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
if(v)x=-x;
}
int main()
{
qr(n);
for(int i=0;i<n;i++)qr(a[i]);
sort(a,a+n);
p=(n>>1)-1;
for(int i=0;i<p;i++)ans+=a[p]-a[i];
for(int i=p+1;i<n;i++)ans+=a[i]-a[p];
printf("%lld
",ans);
return 0;
}
方法2（第k小数）：
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define g getchar()
using namespace std;
const int N=1e5+10;
void qr(int &x)
{
char c=g;x=0;
while(!('0'<=c&&c<='9'))c=g;
while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
}
int a[N],n,k;
int random(int x){return rand()%x;}//取[0,x-1]中的数
int find(int l,int r)//查基准值排名
{
int p=random(r-l+1)+l,x=a[p];//随机基准值。
swap(a[l],a[p]);
while(l<r)
{
while(a[r]>=x&&l<r)--r;
a[l]=a[r];
while(a[l]<=x&&l<r)++l;
a[r]=a[l];
}
a[l]=x;
return l;
}
int dfs(int l,int r)//返回第k小数
{
int t=find(l,r);
if(t<k)return dfs(t+1,r);
else if(t==k)return a[t];
else return dfs(l,t-1);
}
int main()
{
srand(time(0));
qr(n);k=(n+1)>>1;
for(int i=1;i<=n;i++)qr(a[i]);
int p=dfs(1,n);
long long ans=0;
for(int i=1;i<k;i++)ans+=p-a[i];
for(int i=k+1;i<=n;i++)ans+=a[i]-p;
printf("%lld
",ans);
return 0;
}
这是运用分治的思想。
但是，可能大家会不理解find函数为什么就能把[l,r]分成不大于基准值和不小于基准值的两块。不要急，且听我娓娓道来~~
int find(int l,int r)//查基准值排名
{
int p=random(r-l+1)+l,x=a[p];//随机基准值。
swap(a[l],a[p]);
while(l<r)
{
while(a[r]>=x&&l<r)--r;
a[l]=a[r];
while(a[l]<=x&&l<r)++l;
a[r]=a[l];
}
a[l]=x;
return l;
}
首先，我们可以看出x就是选出的随机基准值。
次之，我们可以用赋值环来解释这样做的正确性。
设第i次进入循环，执行第一个赋值时的，执行第二个赋值时的，一共进入k次循环。
如果我们把赋值看作有向边的话，很明显可以想出，图应该是这样的：
最后，我们把的初值赋值给就相当于对(2k+1)个数进行了交换。同时也把[l,r]分成不大于基准值和不小于基准值的两块。