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元起，快前往官网查看详情吧