題目描述

某石油公司計(jì)劃建造一條由東向西的主要輸油管道。該管道要穿過一個(gè)有n口油井的油田。從每口油井都要有一條輸油管道沿最短路徑（或南或北）與主管道相連。如果給定n口油井的位置，及它們的x坐標(biāo)（東西向）和y坐標(biāo)（南北向），應(yīng)如何確定主管道的最優(yōu)位置，即使各油井到主管道之間的輸油管道長(zhǎng)度總和最小的位置？證明可規(guī)定時(shí)間內(nèi)確定主管道的最優(yōu)位置。
輸入格式：
第一行是油井?dāng)?shù)n（1<=n<=10000）
接下來n行是油井的位置,每行2個(gè)整數(shù)x和y(-10000<=x,y<=10000)
輸出格式：
只有一行是油井到主管道之間的輸油管道最小長(zhǎng)度總和


我的思路：先建一個(gè)坐標(biāo)系，然后是上北下南左西右東。
主管東西走向，即與x軸平行，故油井到管道的距離與點(diǎn)的x值無關(guān)，存y值即可(即將點(diǎn)投影到y(tǒng)軸)
問題就簡(jiǎn)化為在y軸上找一點(diǎn)使之到所有點(diǎn)的距離最短。
如有-2 0 3 4，所求點(diǎn)可以是0,1,2,3，最短距離為6+3=9。ps：6=4- -2，3=3-0

#include<stdio.h> #include<algorithm> using namespace std; int main(){int t,a[10002],i,x;scanf("%d",&t);int dis=0;for(i=0;i<t;i++)scanf("%d%d",&x,&a[i]);//x是無用的sort(a,a+t);t--;for(i=0;i<t;)dis+=a[t--]-a[i++];printf("%d\n",dis);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P1862的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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