HDU4311 Meeting point

題意：

給定n個點，選其中的一個點作為起點，然後使其他點到這個點的曼哈頓距離最小，求這個最小的距離

分析：

我們設P作為這個點作為起點

然後 ans = sum(abs|pi.x-p.x|+|pi.y-p.y| )（1<=i<=n）

我們可以對其分別按x,y進行排序，就可以去掉絕對值符號

然後化簡後的公式就可以變成

設這個點在按x排完序後的位置為i;

設tot[i],表示到序號i為止的點的橫坐標的和。

ansx = (i-1)*p.x+(tot[n]-tot[i])-(n-i)*p.x

同理可以求出

設這個點在按t排完序後的位置為i;

ansy= (i-1)*p.y+(tot[n]-tot[i])-(n-i)*p.y

ans = ansx + ansy

然後取最小的ans 即可

時間復雜度為O(nlog(n));

代碼如下：

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int maxn = 1e5+10;

struct point{
    int x,y;
    LL sum;
}p[maxn];

bool cmp1(point A,point B)
{
    if(A.x= 1; --i) {
            p[i].sum += sum - (n-i) * p[i].x;
            sum += p[i].x;
        }
        sum = 0;
        sort(p+1, p+1+n, cmp2);
        for (LL i = 1; i <= n; ++i) {
            p[i].sum += (i-1) * p[i].y -sum;
            sum += p[i].y;
        }
        sum = 0;
        LL ans = 1LL<<62;
        for (LL i = n; i >= 1; --i) {
            p[i].sum += sum - (n-i) * p[i].y;
            ans = min(ans, p[i].sum);
            sum += p[i].y;
        }
        printf(%I64d
,ans);
    }
    return 0;
}