首页 > 代码库 > 1076: 最短距离

1076: 最短距离

2024-10-31 05:32:39   205人阅读

题目描述

在河边有N户人家，他们每天都需要到河边去打水，后来政府拔款给大家修建一个水库。
每户人家到水库的最短距离为沿河方向的距离差，问如何选择水库的位置，使所有人到水库的距离和最短？

输入

第一行输入一个数字Case，表示一共有多少组测试数据。
接下来Case个测试数据块。
每个测试数据块：第一行一个数字N，表示有N户人。
接下来一行有N个数字d，表示每户人家在河流方向上的坐标。
Case<=10，1<=N<=100000，0<=d<=2*10^9。

输出

对于每组测试数据，输出最短的距离和，一行一个结果。

样例输入

221 313

样例输出

20

提示

 

来源

#include<stdio.h>
#include<string.h>
sortquickly(int a[],int lenth)
{
    int mid;
    mid = a[0];
    int i,j;
    i=0;
    j=lenth-1;
    if(lenth>1)
    {
        while(i<j)
        {
            for(;j>i;j--)
            {
                if(a[j]<mid)
                {
                    a[i++]=a[j];
                    break;
                }
            }
            for(;i<j;i++)
            {
                if(a[i]>mid)
                {
                    a[j--]=a[i];
                    break;
                }
            }
        }
        a[i]=mid;
        sortquickly(a,i);
        sortquickly(a+i+1,lenth-i-1);
    }
}
main()
{
    int i,a[100001],lenth,N,h,p,o,mid,x,T,j;
    long sum;
    scanf("%d",&T);
    for(j=0;j<T;j++)
    {
    sum=0;
    scanf("%d",&N);
    h=N;
    for(i=0;i<N;i++)
    scanf("%d",&a[i]);
    sortquickly(a,N);
        if(h%2!=0)
    {      
        p=(h-1)/2;
        mid=a[p];
        for(o=0;o<p;o++)
        {
        x=mid-a[o];
        sum=sum+x;
        }
        for(o=p+1;o<h;o++)
        {
        x=a[o]-mid;
        sum=sum+x;
        }
    }
        if(h%2==0)
    {
        p=h/2;
        p=p-1;
        mid=a[p];
        for(o=0;o<p;o++)
        {
        x=mid-a[o];
        sum=sum+x;
        }
        for(o=p+1;o<h;o++)
        {
        x=a[o]-mid;
        sum=sum+x;
        }
    }
        printf("%ld\n",sum);
}
}

 

 

 

第三届“朗讯杯”初级组

1076: 最短距离


联系
我们