PTA上,一直是答案错误,输入的几个样例答案是对的,不明白错在哪?
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 证明可在线性时间内确定主管道的最优位置。
给定n口油井的位置, 计算各油井到主管道之间的输油管道最小长度总和。
#include<iostream>
using namespace std;
struct location{
int x;
int y;
};
float yresult(location a[],int n)
{
float r;
if(n%2==0)
{
r=1.0/2*(a[n/2].y+a[n/2+1].y);
}
else
r=static_cast<float>(a[(n+1)/2].y);
return r;
}
float length(location a[],int n)
{
float sum1=0,s=0;
float sum2=0,s1=0;
float l=yresult(a,n);
if(n%2==0)
{
for(int i=1;i<=n/2;i++)
{
sum1=l-a[i].y;
sum2=sum2+sum1;
}
for(int i=n/2+1;i<=n;i++)
{
s=a[i].y-l;
s1=s1+s;
}
return s1+sum2;
}
else
{
for(int i=1;i<(n+1)/2;i++)
{sum1=l-a[i].y;
sum2=sum2+sum1;}
for(int i=n/2+2;i<=n;i++)
{
s=a[i].y-l;
s1=s1+s;
}
return s1+sum2;
}
}
int main()
{
location a[10000];
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n-i;j++)
{
if(a[j].y>a[j+1].y)
{
int temp=a[j].y;
a[j].y=a[j+1].y;
a[j+1].y=temp;
}
}
}
float p=length(a,n);
cout<<p<<endl;
return 0;
}