4.3 提升题 - B Distance of Triples

公司主营业务：网站制作、成都网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出吴忠免费做网站回馈大家。

原题目为英文,不好看,我放翻译过的.

题意：

根据谷歌翻译:给定(自己输入)三个集合s1,s2,s3，定义D（a，b，c）=|a-b|+|b-c|+|c-a|，

假设其中a，b，c分别来自三个集合s1，s2，s3，求出使D最小且三元组（a，b，c）大的a，b，c的值和对应的D。

思路：

在数轴上点出几个个任意点a，b，c，a1，a2，c1，c2如下

—a1——————a——————a2———————b————c2———c—————c1——

假设它们的关系如上，考虑某一个b。容易发现，中间的b只要在a和c之间移动，不改变D的大小，所以我们只需要考虑a和c即可。如果a→a1或c→c1，D变大，只有a和c在数轴上向b靠拢，且不越过b才会使D变小。故有一个思路如下：

思路一、

找到元素最少的数组（这一部我实现起来有点麻烦，就不搞了），假设为s2，把s1和s2排序，固定b，找到b在s1和s2中的位置，以便找到数轴上距离b最近的a和c，这样处理s2中每一个b，比较一下D（a，b，c）即可。

因为在做的途中我找到了我思路的问题，有可能对某个b在s1和s3中找不到比b大或小的数；

而且写好的程序错误也很多，就没做了，过几日看懂了标答再补发，最近在预习数据结构和学习递归函数

//根据谷歌翻译:给定数集 s1,s2,s3，要求(a∈s1,b∈s2,c∈s3)|a−b|+|b−c|+|c−a|的最小值,|s1,s2,s3|≤10^4
#include
#include
#include
#define max 10000
int Dis(int a,int b,int c)
{
  return abs(a-b)+abs(b-c)+abs(a-c);
}
int find(int arr[],int x,int len)//寻找x在数组arr中的位置(分别传入数组,待查找的值,数组长度)
{
  int a, b, c;
  a = 0, c = len;
  while (1)
  {
  b = (a + c) / 2;
  if (x == arr[b] || abs(a - c) == 1) return b;
  else if (x >arr[b]) a = b;
  else if (x< arr[b]) c = b;
  }
}
void swap(int* a, int* b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}
void func(int arr[], int len)//选择排序,升序
{
  int i, j;

  for (i = 0; i< len - 1; i++)
  {
  int min = i;
  for (j = i + 1; j< len; j++)
  if (arr[j]< arr[min])
  min = j;
  swap(&arr[min], &arr[i]);
  }
}
int main()
{
  char check=0;
  int i=0,j=0,n1,n2,n3,s1[max]={0},s2[max]={0},s3[max]={0},a,b,c,D,a2,b2,c2;
  scanf("%d %d %d",&n1,&n2,&n3);
 while (check != '\n')
 {
     scanf("%d", &s1[i++]);
     check = getchar();
 }
  check=0,i=0;
 while (check != '\n')
 {
     scanf("%d", &s2[i++]);
     check = getchar();
 }
  check=0,i=0;
 while (check != '\n')
 {
     scanf("%d", &s3[i++]);
     check = getchar();
 }
  //固定s2，把s1和s3排序,选择比b小的a比b大的c
  func(s1,strlen(s1));
  func(s3,strlen(s3));
  //假设第一个b是要求答案
  b=s2[0];
  n3=find(s3,b,strlen(s3));
  a=s1[n3];
  if(s3[n3]==b||n3==strlen(s3)) c=b;
  else c=s3[n3+1];
  D=Dis(a,b,c);
  for(i=1;i   {
  b2=s2[i];
  n3=find(s3,b2,strlen(s3));
  a2=s1[n3];
  if(s3[n3]==b2||n3==strlen(s3)) c2=b2;
  else c2=s3[n3+1];
  if(D>Dis(a2,b2,c2))
 {
 a=a2,b=b2,c=c2;
 }
  }
  printf("MinD(%d,%d,%d)=%d",a,b,c,D);
  return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页名称：每日一题(有点难2022/11/30）12/3-创新互联
标题网址：http://azwzsj.com/article/dijops.html