火车站选址

这道题目是字节跳动2020.9.20的一道题目

题目描述：

A市计划新建一个火车站方便市民出行。

这里的道路十分规整，市民从位置（x1,y1）到位置（x2,y2）的路程为|x1-x2|+|y1-y2|

经过前期考察，初步选定了M个可以建造火车站的位置。

为了尽可能节省市民到达火车站的时间，市长希望新建的车站离每位市民的总路程尽可能的小。

请帮市长选出最适合新建火车站的位置。

输入描述：

第一行有两个整数N，M；分别表示市民的人数和可以建设火车站的位置

后面N行，每行2个整数x_i,y_i,表示第i位市民的居住位置在(x_i,y_i)

后面M行，每行2个整数p_i,q_i,表示第i个火车候站候选位置在(p_i,q_i)

1 <= N <= 100000

1 <= M <= 100000

-10000000 <= x_i , y_i , p_i , q_i <= 10000000

输出描述：

两个整数 p_i , q_i 表示最合适新建火车站的位置，若有多个答案，输出原始数据中第一个出现的

样例输入：

4 3
-1 -1
-1 1
1 -1
1 1
3 2
1 0
0 0

样例输出：

1 0

题目解析：

首先这道题上来看数据n，m都是1e5 ，x，y，p，q分别1e7，显然我们不能用暴力去做

我们就想到给原有的x_i,y_i,在实际运算中其实是独立的，需要去求的是最后的和，所以我们可以将x和y分成两个数组 并排序。那么 我们得到了有序的x，y后 如果给我们一组p，q，如何去计算 总共的花费呢？

此时想到前缀和

对于p来说，我们找到p在x里比p小的位置L1和比p大的位置L2，那么比p小的贡献就是（L1*p）-sum[L1];

sum就是前缀和，比p大的贡献就是sum[n]-sum[L2]-(n-L2)*p;

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;

int xx[100005],yy[10005];
long long sumx[100005],sumy[100005];
int x,y;
int main()
{
    long long minx=9223372036854775807;
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        xx[i]=x;
        yy[i]=y;
    }
    sort(xx,xx+n);
    sort(yy,yy+n);
    sumx[0]=xx[0];
    sumy[0]=yy[0];
    for(int i=1;i<n;i++){
        sumx[i]=sumx[i-1]+xx[i];
        sumy[i]=sumy[i-1]+yy[i];
    }
    int ansx,ansy;
    long long now;
    for(int i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        now=0;
        int ll;
        ll=lower_bound(xx,xx+n,x)-xx;
        now+=(ll)*x-sumx[ll-1];
        ll=lower_bound(yy,yy+n,y)-yy;
        now+=(ll)*y-sumy[ll-1];
        ll=upper_bound(xx,xx+n,x)-xx;
        if(ll<n)now+=(sumx[n-1]-sumx[ll-1])-(n-ll)*x;
        ll=upper_bound(yy,yy+n,y)-yy;
        if(ll<n)now+=(sumy[n-1]-sumy[ll-1])-(n-ll)*y;
        if(now<minx){
            ansx=x;
            ansy=y;
            minx=now;
        }
    }
    cout<<ansx<<' '<<ansy<<endl;
    return 0;
}