2 条题解
-
1
我在做这道题的时候并没有看到
任意两家商店均不在同一位置,也不相邻(距离为 1 即相邻)。的限制,因此我认为我的这个做法即使没有这个限制也能通过。首先根据一维货仓选址的结论,最优的是中位数。但是我们找到的最有位置可能被占用,所以考虑枚举:
若 为奇数,且最优位置被商店占用,我们当然希望移动的越小越好,所以考虑与它曼哈顿距离为 的点。
但是因为我没有看到限制,所以这些点也可能被占用,所以我们枚举一个范围内的点,并判定是否更优。
设 的中位数为 , 的中位数为 ,则我们考虑 到 之间的点,这之中一定存在至少一个点不被占用。而我们希望所选的最终点离 比较近,否则不优,所以选择这部分。
若 为偶数,且最优范围大小 ,则考虑所有点,检查是否在最优范围内。
若最优范围大小 ,则沿用 为奇数的做法。设最优范围为 到 ,则枚举 到 之间的点。这里其实可以再小一点,但是我没有算。
至于判定,可以二分。总复杂度 。非常劣,调一调 为偶数时的枚举范围应该能到 。
说实话感觉这个做法比较猎奇。#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
货仓选址(二维)题解
题意简述
在二维平面上选择一个合适的点,到N个点的曼哈顿距离之和最小。求离之和的最小值、合适的点位置数目。
分析
从一维的货仓选址得到启发,合适的点应该是位置上的中位数,那么二维也是一样,把x坐标y坐标都排序,再分奇偶讨论,如果是奇数,这样的点(分析至此)就只有一个;如果是偶数,这样的点就是n/2和n/2+1之间横竖线条的交点个数(分析至此)。
悲伤
说“分析至此”的原因是还需要考虑到 “任意两家商店均不在同一位置,也不相邻(距离为 1 即相邻)”。需要特殊处理这些特殊的情况。。。
警示liuyundi以后要认真审题。。。
- 1
信息
- ID
- 80
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 149
- 已通过
- 11
- 上传者