2 条题解

  • 1
    @ 2026-9-24 13:17:38

    我在做这道题的时候并没有看到任意两家商店均不在同一位置,也不相邻(距离为 1 即相邻)。的限制,因此我认为我的这个做法即使没有这个限制也能通过。

    首先根据一维货仓选址的结论,最优的是中位数。但是我们找到的最有位置可能被占用,所以考虑枚举:

    若 NN 为奇数,且最优位置被商店占用,我们当然希望移动的越小越好,所以考虑与它曼哈顿距离为 11 的点。

    但是因为我没有看到限制,所以这些点也可能被占用,所以我们枚举一个范围内的点,并判定是否更优。

    设 XX 的中位数为 XmX_m,YY 的中位数为 YmY_m,则我们考虑 (Xm−N2,Ym−N2)(X_m-\frac{\sqrt N}{2},Y_m-\frac{\sqrt N}{2}) 到 (Xm+N2,Ym+N2)(X_m+\frac{\sqrt N}{2},Y_m+\frac{\sqrt N}{2}) 之间的点,这之中一定存在至少一个点不被占用。而我们希望所选的最终点离 (Xm,Ym)(X_m,Y_m)比较近,否则不优,所以选择这部分。

    若 NN 为偶数,且最优范围大小 >N> N ,则考虑所有点,检查是否在最优范围内。

    若最优范围大小 ≤N\le N,则沿用 NN 为奇数的做法。设最优范围为 (Xp,Yp)(X_p,Y_p) 到 (Xq,Yq)(X_q,Y_q),则枚举 (Xp−N2,Yp−N2)(X_p-\frac{\sqrt N}{2},Y_p-\frac{\sqrt N}{2}) 到 (Xq+N2,Yq+N2)(X_q+\frac{\sqrt N}{2},Y_q+\frac{\sqrt N}{2}) 之间的点。这里其实可以再小一点,但是我没有算。

    至于判定,可以二分。总复杂度 O(NNlog⁡N)O(N \sqrt N \log N)。非常劣,调一调 NN 为偶数时的枚举范围应该能到 O(Nlog⁡N)O(N \log N)。

    说实话感觉这个做法比较猎奇。

    #include<bits/stdc++.h>
    using namespace std;
    //#define int long long
    #define lb(x) x&(-x)
    #define ls(p) (p<<1)
    #define rs(p) ((p<<1)|1)
    #define pii pair<int,int>
    #define F first
    #define S second
    #define mkp make_pair 
    #define psb push_back
    #define vi vector<int>
    
    const int mod=998244353;
    const int N=1e4+1000,inf=1e9,Dt=2e7;
    int n,X[N],Y[N];
    int H(int x,int y){
    	x=x+10000,y=y+10000;
    	return (x<<14)|y;
    }bitset<400000000>mp;
    int sumx[N],sumy[N];
    pii sav[N];
    int chk(int ax,int ay){
    	int l=1,r=n;
    	int ret=0;
    	while(l<r){
    		int mid=((l+r+1)>>1);
    		if(X[mid]<=ax) l=mid;
    		else r=mid-1;
    	}ret=ret+l*ax-sumx[l]+sumx[n]-sumx[l]-(n-l)*ax;
    	
    	l=1,r=n;
    	while(l<r){
    		int mid=((l+r+1)>>1);
    		if(Y[mid]<=ay) l=mid;
    		else r=mid-1;
    	}ret=ret+l*ay-sumy[l]+sumy[n]-sumy[l]-(n-l)*ay;
    	return ret;
    }
    signed main(){
    //	system("fc 货仓选址ex.out 货仓选址ex.ans");return 0;
    //	freopen("货仓选址ex.in","r",stdin);
    //	freopen("货仓选址ex.out","w",stdout);
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>X[i]>>Y[i];
    		sav[i]=mkp(X[i],Y[i]);
    		mp[H(X[i],Y[i])]=1;
    	}sort(X+1,X+n+1);
    	sort(Y+1,Y+n+1);
    	for(int i=1;i<=n;i++){
    		sumx[i]=sumx[i-1]+X[i];
    		sumy[i]=sumy[i-1]+Y[i];
    	}
    	if(n&1){
    		int Xm=X[n/2+1],Ym=Y[n/2+1];
    		int minn=inf,mins=0;
    		for(int ix=Xm-50;ix<=Xm+50;ix++){
    			for(int iy=Ym-50;iy<=Ym+50;iy++){
    				if(mp[H(ix,iy)]) continue;
    				int v=chk(ix,iy);
    				if(v<minn) minn=v,mins=0;
    				if(v==minn) mins++;
    			}
    		}
    		cout<<minn<<" "<<mins;
    	}else{
    		int Xm1=X[n/2],Xm2=X[n/2+1],Ym1=Y[n/2],Ym2=Y[n/2+1];
    		int minn=inf,mins=0;
    		
    		if((Xm2-Xm1+1)*(Ym2-Ym1+1)>n){
    			minn=chk(Xm1,Ym1);mins=(Xm2-Xm1+1)*(Ym2-Ym1+1);
    			for(int i=1;i<=n;i++){
    				if(sav[i].F>=Xm1&&sav[i].F<=Xm2&&sav[i].S>=Ym1&&sav[i].S<=Ym2) mins--;
    			}cout<<minn<<" "<<mins;
    		}else{
    			for(int ix=Xm1;ix<=Xm2;ix++){
    				for(int iy=Ym1;iy<=Ym2;iy++){
    					if(mp[H(ix,iy)]) continue;
    					int v=chk(ix,iy);
    					
    					if(v<minn) minn=v,mins=0;
    					if(v==minn) mins++;					
    				}
    			}
    			if(minn==inf){
    				for(int ix=Xm1-50;ix<=Xm2+50;ix++){
    					for(int iy=Ym1-50;iy<=Ym2+50;iy++){
    						if(mp[H(ix,iy)]) continue;
    						int v=chk(ix,iy);
    						if(v<minn) minn=v,mins=0;
    						if(v==minn) mins++;	
    					}
    				}
    			}
    			cout<<minn<<" "<<mins;
    		}
    	}
    	return 0;
    } 
    
    • 0
      @ 2025-3-15 10:45:10

      货仓选址(二维)题解

      题意简述

      在二维平面上选择一个合适的点,到N个点的曼哈顿距离之和最小。求离之和的最小值、合适的点位置数目。

      分析

      从一维的货仓选址得到启发,合适的点应该是位置上的中位数,那么二维也是一样,把x坐标y坐标都排序,再分奇偶讨论,如果是奇数,这样的点(分析至此)就只有一个;如果是偶数,这样的点就是n/2和n/2+1之间横竖线条的交点个数(分析至此)。

      悲伤

      说“分析至此”的原因是还需要考虑到 “任意两家商店均不在同一位置,也不相邻(距离为 1 即相邻)”。需要特殊处理这些特殊的情况。。。

      警示liuyundi以后要认真审题。。。

      • 1

      信息

      ID
      80
      时间
      1000ms
      内存
      512MiB
      难度
      9
      标签
      (无)
      递交数
      149
      已通过
      11
      上传者