第一行，一个整数N，表示点数。 接下来N行，每行一个整数X_i，表示点的坐标。
一个整数，表示线段的总长。
5
1
5
3
2
4


40
提示
N  < =  10000  ,  0  < =  X_i  < =  1000000000

求处理。

这个可以参考选择排序的原理，逐一累加即可。

能说的详细点吗，我不懂呀。。。

//X_i[N];
//int i,j;
//int sum=0;
for(i=0;i<N-1;i++)
{
    for(j=i+1;j<N;j++)
    {
        sum+=abs(X_i[j]-X_i[i]);
    }
}

我还是不懂啊。。。这个数据好大。。怎么解决呢？

好大？没有输入的设置为负数或者零不计算就可以了。

int n;
scanf("%d",&n);

int X_i[1000]={0};

int i,j;

for(i=1;i<=n;i++)
{
    scanf("%d",&X_i[i-1]);
}

int sum=0;
for(i=0;i<n-1;i++)
{
    for(j=i+1;j<n;j++)
    {
        sum+=abs(X_i[j]-X_i[i]);
    }
}

printf("\n%d\n",sum);

[此贴子已经被作者于2016-2-29 19:49编辑过]

这是一道有趣的题目
因为N<=10000，所以即使傻乎乎的死算也可以得到答案
假如考虑一下算法，可以将要求变换成一个个相邻线段的和
…略…，对于排序好的n个点，得到n-1个线段，每个线程会重复i*(n-i)次
以n=5为例，有4条线段，长度分别是a、b、c、d，那么最终结果是 1*(5-1)*a + 2*(5-2)*b + 3*(5-3)*c + 4*(5-4)*d 再乘以2

从上面的公式可以看出，最中间的系数最大，让最中间一个线段最长（1000000000）时，结果最大，即 10000/2 * 10000/2 * 1000000000 * 2 = 50000000000000000
50000000000000000 需要 56bits 存储，因此选用 unsigned long long 类型

最终代码如下

#include <stdio.h>
#include <stdlib.h>

static int compare_unsigned_( const void* a_, const void* b_ )
{
    unsigned a = *(unsigned*)a_;
    unsigned b = *(unsigned*)b_;
    if( a < b )
        return -1;
    if( a > b )
        return +1;
    return 0;
}

unsigned long long foo( unsigned x[], unsigned n )
{
    if( n < 2 )
        return 0;
    qsort( x, n, sizeof(*x), &compare_unsigned_ );

    unsigned long long length = 0;
    for( unsigned i=1; i<=n-1; ++i )
        length += i*(n-i) * 1ull * (x[i]-x[i-1]);
    return length*2;
}

int main( void )
{
    unsigned x[10000], n;
    scanf( "%u", &n );
    for( unsigned i=0; i!=n; ++i )
        scanf( "%u", x+i );

    printf( "%llu\n", foo(x,n) );
    return 0;
}

当然，因为数据量还是比较小的（N<=10000），不做算法优化也可以

#include <stdio.h>

unsigned long long foo( unsigned x[], unsigned n )
{
    if( n < 2 )
        return 0;

    unsigned long long length = 0;
    for( unsigned i=0; i!=n-1; ++i )
        for( unsigned j=i+1; j!=n; ++j )
            length += x[j]>=x[i] ? x[j]-x[i] : x[i]-x[j];
    return length*2;
}

int main( void )
{
    unsigned x[10000], n;
    scanf( "%u", &n );
    for( unsigned i=0; i!=n; ++i )
        scanf( "%u", x+i );

    printf( "%llu\n", foo(x,n) );
    return 0;
}

都是大神啊！太厉害了你们！