51nod oj 1096 1108 1110距离之和最小【一维---三维中位数--水】

题目链接：​​1096​​

代码：

#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
#define LL long long
LL shu[10100];
LL s,mid,ans;
int main()
{
  int n;scanf("%d",&n);
  for (int i=1;i<=n;i++)
    scanf("%lld",&shu[i]);
  sort(shu+1,shu+n+1);
  if (n%2)
  {
    mid=shu[n/2+1];
    s=0;
    for (int i=1;i<=n;i++)
    s+=abs(mid-shu[i]);
    printf("%lld",s);
  }
  else
  {
    mid=(shu[n/2]+shu[n/2+1])/2;
    s=0;ans=0;
    for (int i=1;i<=n;i++)
    s+=abs(mid-shu[i]);
    mid++;
    for (int i=1;i<=n;i++)
    ans+=abs(mid-shu[i]);
    printf("%lld\n",min(s,ans));
  }
  return 0;
}      

传送门：​​1108​​

代码“：

#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
int x[10100],y[10100],z[10100];
int main()
{
  int n;scanf("%d",&n);
  for (int i=1;i<=n;i++)
  scanf("%d%d%d",&x[i],&y[i],&z[i]);
  sort(x+1,x+1+n); 
  sort(y+1,y+1+n);
  sort(z+1,z+1+n);
  if (n%2)
  {
    int xx=x[n/2+1];
    int yy=y[n/2+1];
    int zz=z[n/2+1];
    long long s=0;
    for (int i=1;i<=n;i++)
    s+=abs(xx-x[i])+abs(yy-y[i])+abs(zz-z[i]);
    printf("%lld\n",s);
  }
  else
  {
    int xx=(x[n/2]+x[n/2+1])/2;
    int yy=(y[n/2]+y[n/2+1])/2;
    int zz=(z[n/2]+z[n/2+1])/2;
    long long s=0,ss=0;
    for (int i=1;i<=n;i++)
    {
      s+=abs(xx-x[i])+abs(yy-y[i])+abs(zz-z[i]);
      ss+=abs(xx+1-x[i])+abs(yy+1-y[i])+abs(zz+1-z[i]);
    }
    s=min(s,ss);
    printf("%lld\n",s);
  }
  return 0;
}      

题目链接：

​​1110​​

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
struct node{
  LL x,y;
}pp[12000];
bool cmp(node xx,node yy)
{
  return xx.x<yy.x;
}
int n;
LL zhao(int xx)
{
  LL lp;
  for (int i=0;i<n;i++)
  {
    if (pp[i].y>=xx)
    {
      lp=pp[i].x;break;
    }
    else
      xx-=pp[i].y;
  }
  return lp;
}
int main()
{
  int p;
  p=0;scanf("%d",&n);
  for (int i=0;i<n;i++)
  {
    scanf("%lld%lld",&pp[i].x,&pp[i].y);
    p+=pp[i].y;
  }
  sort(pp,pp+n,cmp);
  LL k1,k2,k3,s,s1=0,s2=0,s3=0;
  if (p%2==1)
  {
    k1=k2=k3=zhao(p/2+1);
  }
  else
  {
    k1=(zhao(p/2+1)+zhao(p/2))/2;
    k2=k1+1;k3=k1-1;
  }
  for (int i=0;i<n;i++)
  {
    s1+=abs(k1-pp[i].x)*pp[i].y;
    s2+=abs(k2-pp[i].x)*pp[i].y;
    s3+=abs(k3-pp[i].x)*pp[i].y;
  }
  s=min(s1,min(s2,s3));
  printf("%lld\n",s);
  return 0;
}