题目: 输油管道问题(洛谷)
这道题是简单的中位数,经典的输油管道问题 此题是中位线到各个点的距离之和最短 #include<bits/stdc++.h> using namespace std; int const N=1e4+7; struct L{ int x,y; friend bool operator<(L a,L b){ return a.y < b.y ; } }a[N]; int n,ans; int main(){ cin >> n; for(int i=1;i<=n;++i){ cin >> a[i].x >> a[i].y ; } sort(a+1,a+n+1); int z=0; if(n%2==1) z=a[n/2+1].y ; else{ z=(a[n/2].y +a[n/2+1].y )/2; } for(int i=1;i<=n;++i){ ans+=abs(z-a[i].y); } cout << ans; return 0; }
//此题还可以用模拟退火做(还没学) 参考博客