在一條數(shù)軸上有N頭牛在不同的位置上，每頭牛都計(jì)算到其它各頭牛的距離。求這n*(n-1)個(gè)距離的總和。1<= N <= 10000。每頭牛所在位置是一個(gè)范圍在0到1,000,000,000之內(nèi)的整數(shù)。

/***********************************************************************\

此題坑在取值上，10000個(gè)數(shù)，超過(guò)了二次循環(huán)的范圍，但這里的二次循環(huán)是指從一開(kāi)始的循環(huán)，所以思路如下

輸入數(shù)組之后，對(duì)數(shù)組進(jìn)行排序

例：

1 2 3 6 9
1:1-1 2-1 3-1 6-1 9-1
2:2-1 2-2 3-2 6-2 9-2
3:3-1 3-2 3-3 6-3 9-3
6:6-1 6-2 6-3 6-6 9-6
9:9-1 9-2 9-3 9-6 9-9

注意，排過(guò)序后，再次計(jì)算距離就會(huì)有0之后的數(shù)（即紅字之后的數(shù)）這些數(shù)在下面一定有對(duì)應(yīng)的數(shù)，這些數(shù)無(wú)需再次計(jì)算，乘二即可。

所以二次循環(huán)可用

代碼實(shí)現(xiàn)如下：

#include<iostream> #include<algorithm> using namespace std; int main() { long long m,n,p,q,a[26666],sum=0; cin>>m; for(int i=1;i<=m;i++) { cin>>a[i]; } sort(a+1,a+m+1); for(int i=1;i<=m;i++) { for(int j=i;j<=m;j++) { p=a[i]-a[j]; p=p*-1; sum=sum+p; } } cout<<sum*2<<endl; } return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/supersumax/p/5882472.html

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的大牛的距离（笑cry）精简算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。