火車站選址
這道題目是位元組跳動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/qukuanlian/107992.html
標籤：區塊鏈