我之前有平均数做的,发现当四个数之间相差很大时就不行
例:1 1 1 21
平均数是6,所以答案是5+5+5+15=30
而中位数是1,答案是0+0+0+20=20
中位数更优
证明中位数比平均数更优
设平均数是avg
平均数的答案是(下面的不等式是三角绝对值不等式)
$|a-avg|+|b-avg|+|c-avg|+|d-avg|$
$>=|a+b-2\*avg|+|d+c-2\*avg|$
$=|2\*avg-(a+b)|+|d+c-2\*avg|$
$>=|d+c-a-b|$
$=d+c-a-b$
中位数的答案是
$|a-b|+|b-b|+|c-b|+|d-b|$
$=b-a+c-b+d-b$
$=d+c-b-a$
所以中位数的答案小于平均数
中位数更优
#include <iostream>
#include <algorithm>
using namespace std;
long long re[150][150];
int n,m;
int main()
{
int t;cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>re[i][j];
long long ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
long long sum[]={re[i][j],re[i][m-j+1],re[n-i+1][j],re[n-i+1][m-j+1]};
sort(sum,sum+4);
ans+=(sum[2]+sum[3]-sum[0]-sum[1]);
}
cout<<ans/4<<endl;}
return 0;
}
哇老哥,终于看到自己的反例了。。。但是为啥呀中位数更优啊
证明的题解发布了