©2020-2024 ioDraw All rights reserved
#include<iostream> #include<algorithm> using namespace std; //输油管道问题 int
main() { int n;//油井的数量 int x;//x坐标，读取后丢弃 int a[1000];//y坐标
cout<<"请输入油井个数："<<endl; cin>>n; cout<<"请输入油井的x和y坐标，以空格分隔："<<endl; for(int
k=0;k<n;k++) cin>>x>>a[k]; sort(a,a+n);//按升序排序 //计算各油井到主管道之间的输油管道最小长度总和 int
min=0; for(int i=0;i<n;i++){ min+=(int)abs(a[i]-a[n/2]); }
cout<<"各油井到主管道之间的输油管道最小长度总和为："<<endl; cout<<min<<endl; }
#include<iostream> #include<algorithm> using namespace std; //输油管道问题 int
a[1024]; //采用分治策略找出第k小元素的算法 //在a[left:right]中选择第k小的元素 int select(int left,int
right,int k){ //找到了第k小的元素 if(left>=right)return a[left]; int i=left;//从左到右的指针
int j=right+1;//从右到左的指针 //把最左边的元素作为分界数据 int pivot=a[left];
//把左侧>=pivot的元素与右侧<=pivot额元素交换 while(true){ //在左侧寻找>=pivot的元素 do{ i=i+1;
}while(a[i]<pivot); //在右侧寻找<=pivot的元素 do{ j=j-1; }while(a[j]>pivot);
if(i>=j)break;//没有发现交换对象 swap(a[i],a[j]); } if(j-left+1==k)return pivot;
a[left]=a[j];//存储pivot a[j]=pivot; if(j-left+1<k) //对一个段进行递归调用 return
select(j+1,right,k-j+left-1); else return select(left,j-1,k); } int main() {
int n;//油井的数量 int x;//x坐标，读取后丢弃 cout<<"请输入油井个数："<<endl; cin>>n;
cout<<"请输入油井的x和y坐标，以空格分隔："<<endl; for(int k=0;k<n;k++) cin>>x>>a[k]; int
y=select(0,n-1,n/2);//采用分治算法计算中位数 //计算各油井到主管道之间的输油管道最小长度总和 int min=0; for(int
i=0;i<n;i++) min+=(int)abs(a[i]-y); cout<<"各油井到主管道之间的输油管道最小长度总和为："<<endl;
cout<<min<<endl; }