**HINT 1:** Sắp xếp tăng dần riêng hoành độ và tung độ.<br>
**HINT 2:** Tạo $2$ mảng pre và next chuẩn bị để tính tổng khoảng cách từ hoành độ $a[i]$ đến các hoành độ trước và sau $a[i]$.<br>
#**HƯỚNG DẪN:**
- Nhận xét: Xét khoảng cách từ $1$ điểm tới $n$ điểm, ta nhận thấy các hàng và cột đều độc lập, nên có thể xử lý riêng tìm khoảng cách min từng cái.<br>
- Sắp xếp tăng dần các hàng, cột giúp dồn các phần tử bé hơn về bên trái, lớn hơn về bên phải, tiện tính toán hơn.<br>
- Xét mảng a gồm n hoành độ đã được sắp xếp, ta cần chọn hoành độ x sao cho khoảng cách x đến các phần tử là nhỏ nhất:
+ Chọn khoảng của $x: a[i] -> a[i+1].$ (gọi $A$ là số phần tử nhỏ hơn $x,B$ là số phần tử lớn hơn $x.$
+ Khi đó khoảng cách từ $a$ tới các phần tử:<br>
$[(x-a[i]) + (x-a[i-1])+...+(x-a[0])]+[(a[i+1]-x)+(a[i+2]-x)+...]$<br>
$= [(x-a[i]) + (x-a[i]) + (a[i]-a[i-1]) + (x-a[i])+(a[i]-a[i-2])+...+(x-a[i])+(a[i]-a[0])]+[(a[i+1]-x)+(a[i+1]-x) + (a[i+1]-a[i+2])+....]$<br>
$=A\*(x-a[i])+B\*(a[i+1]-x)+const(không đổi)$
$=A\*(x-a[i])+B\*(a[i+1]-a[i]) - B\*(x-a[i])+const$
$=(A-B)*(x-a[i]) + const$
+ Nếu $A>=B$ thì cần chọn $x-a[i]$ nhỏ nhất hay $x=a[i]$
+ Nếu $A<B$ thì cần chọn $x-a[i]$ lớn nhất hay $x=a[i+1]$
- Tóm lại các mốc cần xét để tổng nhỏ nhất là các phần tử của $a$.
- Tạo $2$ mảng chuẩn bị $pre,next. pre[i],next[i]$ là khoảng cách $a[i]$ tới các phần tử nhỏ hơn và lớn hơn.
Khi đó theo tính toán bên trên, $pre[i]=pre[i-1]+(x-a[i-1])\*i$
- $ansa$ là khoảng cách nhỏ nhất tại tất cả vị trí $a[i], ansb$ tương tự. Khi đó đáp án bài toán là $ansa+ansb.$
##**CODE MẪU:**
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
long long n,a[100005],b[100005],nexta[100005],nextb[100005],prea,preb,ansa,ansb;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i];
}
sort(a,a+n);
sort(b,b+n);
for(int i=n-2;i>=0;i--)
{
nexta[i]=nexta[i+1]+(a[i+1]-a[i])*(n-i-1);
nextb[i]=nextb[i+1]+(b[i+1]-b[i])*(n-i-1);
}
prea=0,preb=0;
ansa=nexta[0],ansb=nextb[0];
for(int i=1;i<n;i++)
{
prea+=(a[i]-a[i-1])*i,preb+=(b[i]-b[i-1])*i;
ansa=min(ansa,prea+nexta[i]),ansb=min(ansb,preb+nextb[i]);
}
ansa=min(ansa,prea),ansb=min(ansb,preb);
cout<<ansa+ansb;
}
```
sharinganvanhoadong
Created at
1 likes