正题

---

题目大意

$n\ast n$的矩阵，给若干个点，求一个位置让这些点的距离和这个位置的曼哈顿距离和最小。

---

解题思路

我们可以将x坐标和y坐标分开来处理。
这样就是一个线性问题了。
我们先定义这个位置为所有x的平均数，然后我们考虑将x左右移动，如果往左一格，那么$ans=ans-lef{t}_{num}+righ{t}_{num}$。这时就左边的越多越好，如果右移，那么右边的越多越好。这样我们就可以得出放在中位数时是最好的。

---

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;//计算答案printf("%lld\n%lld %lld",ans,x[xn],y[yn]); }

总结

以上是生活随笔为你收集整理的nssl1162-农夫约的假期【中位数,贪心】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。