火車站選址

這道題目是位元組跳動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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/108719.html

標籤：其他

上一篇：EDA第一次課＜1117電路圖的繪制＞

下一篇：鴻蒙不是Linux也不是安卓

火車站選址-位元組跳動筆試

火車站選址

這道題目是位元組跳動2020.9.20的一道題目