nyoj_7:街区最短路径问题

时间:2024-07-13 12:32:59

做这题时,先假设目标点在某个位置,然后对其稍微移动dx,dy,分析对ans的影响。最终得,选点时,使一半的横坐标比目标点横坐标小,一半的纵坐标比目标点小,这样得到的ans最小。

题目链接: http://acm.nyist.net/JudgeOnline/problem.php?pid=7

 #include<iostream>
 #include<algorithm>
 #include<numeric>
 using namespace std;
 ;
 int xx[MAX],yy[MAX];
 int main()
 {
     int n;
     cin>>n;
     while(n--)
     {
         int num;
         cin>>num;
         ;i!=num;i++)
             cin>>xx[i]>>yy[i];
         sort(xx,xx+num);
         sort(yy,yy+num);
         ;
         ;i<num/;i++)
             sum+=xx[num--i]-xx[i]+yy[num--i]-yy[i];
         cout<<sum<<endl;
     }
 }