CSU 2131：突然的灵光 （三分法）

1947: 突然的灵光

  Submit Page    Summary    2 Sec 128 Mb 12 10

Description

长者对小明施加了膜法，使得小明每天起床就像马丁的早晨一样。 今天小明早上6点40醒来后发现自己变成了一名高中生，这时马上就要做早操了，小明连忙爬起来 他看到操场密密麻麻的人，突然灵光一闪想到了一个很严肃的问题： 操场上有n个人，第i个人的坐标为(xi, yi)，刚开始每个人都站的很松散，现在想把所有人排成一行平行x轴紧挨着的队伍，求所有人需要移动的曼哈顿距离之和的最小值。

Input

多组测试数据 每组数据第一行一个整数n(1 ≤ n ≤ 105), 表示有n个人 接下来n行每行两个整数xi, yi(−109 ≤ xi, yi ≤ 109)，表示第i个人的坐标

Output

输出最小代价。

Sample Input

3

1 1

2 1

4 1

4

1 1

1 2

2 1

2 2

Sample Output

1

4

Hint

Source

2017年湖南多校对抗赛第12场

        一个人群挑系列，战绩居然还不错，A了4题，放在现场也能Rank 3，大佬都没打？

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct node
{
    int x,y;
} p[100000+10];

int n;

bool cmp(node a,node b)
{
    return a.x<b.x;
}

LL f(int mid)                //求各个点到对应高度的距离和
{
    LL ret=0;
    for(int i=1;i<=n;i++)
        ret+=abs(p[i].y-mid);
    return ret;
}

LL ff(int mid)                //对于一个确定左端点的坐标差的绝对值和
{
    LL ret=0;
    for(int i=1;i<=n;i++)
        ret+=abs(p[i].x-mid-i+1);
    return ret;
}

int main()
{
    while (~scanf("%d",&n))
    {
        int a=1e9,b=-1e9;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            a=min(a,p[i].y); b=max(b,p[i].y);
        }
        sort(p+1,p+1+n,cmp);
        int l=a,r=b,lmid,rmid;
        while (l<r-1)                    //三分高度
        {
            lmid=(l+r)>>1;
            rmid=(lmid+r)>>1;
            if (f(lmid)<=f(rmid)) r=rmid;
                             else l=lmid;
        }
        LL ans=min(f(l),f(r));
        l=p[1].x-n-1; r=p[n].x;
        while (l<r-1)                    //三分起始点
        {
            lmid=(l+r)>>1;
            rmid=(lmid+r)>>1;
            if (ff(lmid)<=ff(rmid)) r=rmid;
                               else l=lmid;
        }
        ans+=min(ff(l),ff(r));
        printf("%lld\n",ans);
    }
    return 0;
}