正題

---

題目大意

$n?n$的矩陣，給若干個(gè)點(diǎn)，求一個(gè)位置讓這些點(diǎn)的距離和這個(gè)位置的曼哈頓距離和最小。

---

解題思路

我們可以將x坐標(biāo)和y坐標(biāo)分開(kāi)來(lái)處理。
這樣就是一個(gè)線性問(wèn)題了。
我們先定義這個(gè)位置為所有x的平均數(shù)，然后我們考慮將x左右移動(dòng)，如果往左一格，那么$ans=ans?lef{t}_{num}+righ{t}_{num}$。這時(shí)就左邊的越多越好，如果右移，那么右邊的越多越好。這樣我們就可以得出放在中位數(shù)時(shí)是最好的。

---

code

#include<cstdio> #include<cmath> #include<algorithm> using namespace std; long long n,m,z,x[100001],y[100001],p,sum_x,sum_y,ans; int main() {scanf("%lld%lld%lld",&n,&m,&z);for(long long i=1;i<=m;i++)scanf("%lld%lld%lld",&x[i],&y[i],&p),ans+=p;sort(x+1,x+1+m);sort(y+1,y+1+m);//排序long long xn=(m+1)/2,yn=(m+1)/2;if(m%2==0) xn=m/2,yn=m/2;//求中位for(long long i=1;i<=m;i++)ans+=(abs(x[xn]-x[i])+abs(y[yn]-y[i]))*z;//計(jì)算答案printf("%lld\n%lld %lld",ans,x[xn],y[yn]); }

總結(jié)

以上是生活随笔為你收集整理的nssl1162-农夫约的假期【中位数,贪心】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。