请问那种竖着的百叶窗怎么说 - 未名空间MITBBS历史存档

请问那种竖着的百叶窗怎么说# Living

d*o2011-09-20 07:09

1 楼

You are given with three sorted arrays ( in ascending order), you are
required to find a triplet ( one element from each array) such that distance
is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then
distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
Please give a solution in O(n) time complexity

C*y2011-09-20 07:09

2 楼

住的公寓标准配置是那个，我想装保温窗帘，房东不让不钻洞，怎么才能做到呢，还是
没啥希望？谢谢

c*e2011-09-20 07:09

3 楼

每次总是移a,b,c中最小的一个？

s*d2011-09-20 07:09

4 楼

vertical blinds

【在 C*********y 的大作中提到】

: 住的公寓标准配置是那个，我想装保温窗帘，房东不让不钻洞，怎么才能做到呢，还是
: 没啥希望？谢谢

z*w2011-09-20 07:09

5 楼

a greedy approach with O(n) time complexity
1. get the first element of a, b and c. let's use x denotes the largest one,
y denotes medium one, z denotes the smallest one.
2. if the distance(x, y) > distance(y, z), move the y to the next number in
the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
if distance(x,y) == distance(y,z) move y and z together to the next number.
3. update the x,y,z with the new value and repeat the procedure above.

p*n2011-09-20 07:09

6 楼

类似的一题：
Given n arrays, find n number such that sum of their differences is
minimum. For e.g. if there are three arrays
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here
the answer is a = 15, b = 13, and c = 14
方法应该是一样的

d*o2011-09-20 07:09

7 楼

这个什么时候停？是不是需要记录一个minDistance？
比如
A= 1,2,3
B= 4,5,6
C= 7,8,9
按照这种方法，移到最后是
x=1
y=6
z=8
distance=7
但是最开始没移的时候distance=6

one,
in

【在 z******w 的大作中提到】

: a greedy approach with O(n) time complexity
: 1. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.
: 2. if the distance(x, y) > distance(y, z), move the y to the next number in
: the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
: if distance(x,y) == distance(y,z) move y and z together to the next number.
: 3. update the x,y,z with the new value and repeat the procedure above.

d*o2011-09-20 07:09

8 楼

好像这道题的思路是这样的。（不知道和你的方法是不是最后的结果一样。没有怎么看
懂你的方法为什么）
假设
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
1. 初始化一个全局最小值minDistance=INT_MAX;当前距离curDistance=0;
2. get the first element of a, b and c. let's use x denotes the largest one,
y denotes medium one, z denotes the smallest one.(a=1,b=4,c=5)
3. 找到最小值a，最开始在B[0],那么我就一直把a往右移，直到a>b (13>4),假设移到
了B[i](这里i=1),计算 B[i]之前的一个数B[i-1](就是B[0])和最大值c的差,(c-B[0]=5
-1=4),这个差就是curDistance,如果curDistance小于minDistance,更新minDistance.
4. 更新a,b,c
5. 重复step 2,3,4，直到全部array已经移到了尾部。

one,
in

【在 z******w 的大作中提到】

: a greedy approach with O(n) time complexity
: 1. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.
: 2. if the distance(x, y) > distance(y, z), move the y to the next number in
: the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
: if distance(x,y) == distance(y,z) move y and z together to the next number.
: 3. update the x,y,z with the new value and repeat the procedure above.

x*52011-09-20 07:09

9 楼

The code: 欢迎验证
int Array::Find_value(vector a, vector b, vector c){
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
std::sort(c.begin(),c.end());
int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
int l=INT_MAX;
while(il=min(l,max(a[i]-b[j],max(b[j]-c[k],c[k]-a[i])));
if(a[i]<=b[j]&&a[i]<=c[k]) i++;
else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
else if(c[k]<=a[i]&&c[k]<=b[j]) k++;
}
return l;
}

k*y2011-09-20 07:09

10 楼

考虑六种从小到大排列的可能情况，每种找出最小的distance，再一起比较。
import random
# generate random data
data = [[],[],[]]
for i in range(0,3):
N = random.randint(5, 10)
for j in range(0, N):
data[i].append(random.randrange(0, 1000))
data[i].sort()
test_cases = [(0,1,2), (0,2,1),
(1,0,2), (1,2,0),
(2,0,1), (2,1,0)]
pos = [[]]*len(test_cases)
dist = [1000000]*len(test_cases)
def LowerBound(x, queueID, start):
for i in range( start, len(data[queueID]) ):
if data[queueID][i] >= x:
return i
return len(data[queueID])
# test the case x <= y <= z with
# x in data[id[0]], y in data[id[1]], z in data[id[2]]
for case in range( 0, len(test_cases) ):
id0, id1, id2 = test_cases[case]
pos1, pos2 = 0, 0
for pos0 in range( 0, len(data[id0]) ):
x = data[id0][pos0]
pos1 = LowerBound(x, id1, pos1)
if pos1 < len(data[id1]):
y = data[id1][pos1]
pos2 = LowerBound(y, id2, pos2)
if pos2 < len(data[id2]):
z = data[id2][pos2]
if dist[case] >= z-x:
dist[case] = z-x
pos[case] = [pos0, pos1, pos2]
else:
break
else:
break
min_case = 0
for case in range( 1, len(test_cases) ):
if dist[case] < dist[min_case]:
min_case = case
print data[0];
print data[1];
print data[2];
q0, q1, q2 = test_cases[min_case]
pos0, pos1, pos2 = pos[min_case]
print 'the minimal distance is ', dist[min_case]
print 'queue ', q0, ' at ', pos0, ' with value ', data[q0][pos0];
print 'queue ', q1, ' at ', pos1, ' with value ', data[q1][pos1];
print 'queue ', q2, ' at ', pos2, ' with value ', data[q2][pos2];

distance

【在 d****o 的大作中提到】

: You are given with three sorted arrays ( in ascending order), you are
: required to find a triplet ( one element from each array) such that distance
: is minimum.
: Distance is defined like this :
: If a[i], b[j] and c[k] are three elements then
: distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
: Please give a solution in O(n) time complexity

z*c2011-09-20 07:09

11 楼

可以把三个数组merge到一个大数组中，同时要保留element from where
用三个变量记录most recent element from each array 从大数组的开始遍历，
假设当前数来自数组A，那么找到它到most recent B and most recent C的距离。然后
更新most recent A。
不知这样对不？

l*y2011-09-20 07:09

12 楼

像楼主说的，每次把最小的往上移。
用了三个指针，分别指向三个数组，中间会交换指针，min, mid, max，他们分别指向
三个从小到到大排列的数，距离就是 *max -*min.
最后return the minimal distance, the vector d records the three elements
with minimal distance.
请指正，谢谢了！
void swap(vector::iterator &a, vector::iterator &b){
vector::iterator temp;
temp=a;

a=b;
b=temp;
}
int min_dist(vector &a, vector &b, vector &c, vector &d){
vector::iterator min=a.begin(), mid=b.begin(), max=c.begin();
int dist=100000; //Make the initial dist large enough.
for(int i=0; i<3; ++i)
{ d.push_back(0);}

while (min!= a.end() && min!= b.end() && min!=c.end()){
if (*min > *mid) swap(min, mid);
if (*mid > *max) swap(mid, max);
if (*min > *mid) swap(min, mid);
int t=*max - *min;
if (dist > t)

{
dist= t;
d[0]=*min;
d[1]=*mid;
d[2]=*max;

}
++min;

}
return dist;
}

【在 c*****e 的大作中提到】

: 每次总是移a,b,c中最小的一个？

H*12011-09-20 07:09

13 楼

1，10， 40
2， 3， 19
5，80， 90
要找三个数的距离之和最小
答案应该是1,3,5
但这种办法不可能找到啊

one,

【在 d****o 的大作中提到】

: 好像这道题的思路是这样的。（不知道和你的方法是不是最后的结果一样。没有怎么看
: 懂你的方法为什么）
: 假设
: A = {4, 10, 15, 20}
: B = {1, 13, 29}
: C = {5, 14, 28}
: 1. 初始化一个全局最小值minDistance=INT_MAX;当前距离curDistance=0;
: 2. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.(a=1,b=4,c=5)
: 3. 找到最小值a，最开始在B[0],那么我就一直把a往右移，直到a>b (13>4),假设移到

b*u2011-09-20 07:09

14 楼

不是找距离和最小，而是max。 125和135是一样的

【在 H*****1 的大作中提到】

: 1，10， 40
: 2， 3， 19
: 5，80， 90
: 要找三个数的距离之和最小
: 答案应该是1,3,5
: 但这种办法不可能找到啊
:
: one,

b*u2011-09-20 07:09

15 楼

最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。

b*v2011-09-20 07:09

16 楼

1, 2, 5也可以吧

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 H*****1 的大作中提到】

: 1，10， 40
: 2， 3， 19
: 5，80， 90
: 要找三个数的距离之和最小
: 答案应该是1,3,5
: 但这种办法不可能找到啊
:
: one,

z*n2011-09-20 07:09

17 楼

每次把（X,Y，Z）中最小的往上移一位，计算一个min distance，得到一个新的（X，Y
，Z），重复以上步骤，最多一共 3N 次可以完成，O(N)

h*y2011-09-20 07:09

18 楼

这个应该好证明吧？

【在 b***u 的大作中提到】

: 最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。

h*y2011-09-20 07:09

19 楼

每次移动最大的，只会让结果更大
移动中间的，最大的不会变
但是，不知道是否一定是全局最优解
大家能够给个证明么？

【在 h*****y 的大作中提到】

: 这个应该好证明吧？

i*h2011-09-20 07:09

20 楼

这个不就是我前两天说的题么?
改头换面又出来了, 果然经典啊.

p*u2011-09-20 07:09

21 楼

nice code!

【在 x*******5 的大作中提到】

: The code: 欢迎验证
: int Array::Find_value(vector a, vector b, vector c){
: std::sort(a.begin(),a.end());
: std::sort(b.begin(),b.end());
: std::sort(c.begin(),c.end());
: int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
: int l=INT_MAX;
: while(i: l=min(l,max(a[i]-b[j],max(b[j]-c[k],c[k]-a[i])));
: if(a[i]<=b[j]&&a[i]<=c[k]) i++;

x*52011-09-20 07:09

22 楼

证明也许比较难，但是我是这样做的：
/*Description: given three arrays A, B,C, find three indices i,j, k such that
the value l=max((a-b),(b-c), (c-a)) is minimized
Input: vector a, vector b, vector c
Output: void
K.O.: sorting, merge sort variant
*/
int Array::Find_value_brute(vector a, vector b, vector c){
int n=a.size(),m=b.size(),p=c.size(),l=INT_MAX;
for(int i=0;ifor(int j=0;jfor(int k=0;k

int ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=abs(c[k]-a[i]);
l=min(l,max(ta,max(tb,tc)));
}
return l;
}
int Array::Find_value(vector a, vector b, vector c){
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
std::sort(c.begin(),c.end());
int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
int l=INT_MAX;
while(iint ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=abs(c[k]-a[i]);
l=min(l,max(ta,max(tb,tc)));
if(a[i]<=b[j]&&a[i]<=c[k]) i++;
else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
else if(c[k]<=a[i]&&c[k]<=b[j]) k++;
}
return l;
}
提出的方法应该和brute force的结果一样，于是
int count=0;
for(int i=0;i<20000;i++){
vector a=Pearl::generate_int_swap(10,100);
vector b=Pearl::generate_int_knuth(10,200);
vector c=Pearl::generate_int_floyd(10,300);
int t1=Array::Find_value_brute(a,b,c);
int t2=Array::Find_value(a,b,c);
if (t1!=t2)
count++;
}
cout<a,b,c是三个长度为10的随即数组，三个函数是我自己写的随即数生成器（idea来自编
程珠玑，所以namespace取的是Pearl）
多次实验，count都是0

d*o2011-09-20 07:09

23 楼

You are given with three sorted arrays ( in ascending order), you are
required to find a triplet ( one element from each array) such that distance
is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then
distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
Please give a solution in O(n) time complexity

c*e2011-09-20 07:09

24 楼

每次总是移a,b,c中最小的一个？

z*w2011-09-20 07:09

25 楼

a greedy approach with O(n) time complexity
1. get the first element of a, b and c. let's use x denotes the largest one,
y denotes medium one, z denotes the smallest one.
2. if the distance(x, y) > distance(y, z), move the y to the next number in
the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
if distance(x,y) == distance(y,z) move y and z together to the next number.
3. update the x,y,z with the new value and repeat the procedure above.

p*n2011-09-20 07:09

26 楼

类似的一题：
Given n arrays, find n number such that sum of their differences is
minimum. For e.g. if there are three arrays
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here
the answer is a = 15, b = 13, and c = 14
方法应该是一样的

d*o2011-09-20 07:09

27 楼

这个什么时候停？是不是需要记录一个minDistance？
比如
A= 1,2,3
B= 4,5,6
C= 7,8,9
按照这种方法，移到最后是
x=1
y=6
z=8
distance=7
但是最开始没移的时候distance=6

one,
in

【在 z******w 的大作中提到】

: a greedy approach with O(n) time complexity
: 1. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.
: 2. if the distance(x, y) > distance(y, z), move the y to the next number in
: the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
: if distance(x,y) == distance(y,z) move y and z together to the next number.
: 3. update the x,y,z with the new value and repeat the procedure above.

d*o2011-09-20 07:09

28 楼

好像这道题的思路是这样的。（不知道和你的方法是不是最后的结果一样。没有怎么看
懂你的方法为什么）
假设
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
1. 初始化一个全局最小值minDistance=INT_MAX;当前距离curDistance=0;
2. get the first element of a, b and c. let's use x denotes the largest one,
y denotes medium one, z denotes the smallest one.(a=1,b=4,c=5)
3. 找到最小值a，最开始在B[0],那么我就一直把a往右移，直到a>b (13>4),假设移到
了B[i](这里i=1),计算 B[i]之前的一个数B[i-1](就是B[0])和最大值c的差,(c-B[0]=5
-1=4),这个差就是curDistance,如果curDistance小于minDistance,更新minDistance.
4. 更新a,b,c
5. 重复step 2,3,4，直到全部array已经移到了尾部。

one,
in

【在 z******w 的大作中提到】

: a greedy approach with O(n) time complexity
: 1. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.
: 2. if the distance(x, y) > distance(y, z), move the y to the next number in
: the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
: if distance(x,y) == distance(y,z) move y and z together to the next number.
: 3. update the x,y,z with the new value and repeat the procedure above.

x*52011-09-20 07:09

29 楼

The code: 欢迎验证
int Array::Find_value(vector a, vector b, vector c){
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
std::sort(c.begin(),c.end());
int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
int l=INT_MAX;
while(il=min(l,max(a[i]-b[j],max(b[j]-c[k],c[k]-a[i])));
if(a[i]<=b[j]&&a[i]<=c[k]) i++;
else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
else if(c[k]<=a[i]&&c[k]<=b[j]) k++;
}
return l;
}

k*y2011-09-20 07:09

30 楼

考虑六种从小到大排列的可能情况，每种找出最小的distance，再一起比较。
import random
# generate random data
data = [[],[],[]]
for i in range(0,3):
N = random.randint(5, 10)
for j in range(0, N):
data[i].append(random.randrange(0, 1000))
data[i].sort()
#=============================
test_cases = [(0,1,2), (0,2,1),
(1,0,2), (1,2,0),
(2,0,1), (2,1,0)]
pos = [[] for i in range(len(test_cases))]
dist = [1000000]*len(test_cases)
def LowerBound(x, queueID, start):
for i in range( start, len(data[queueID]) ):
if data[queueID][i] >= x:
return i
return len(data[queueID])
# test the case x <= y <= z with
# x in data[id[0]], y in data[id[1]], z in data[id[2]]
for case in range( 0, len(test_cases) ):
id0, id1, id2 = test_cases[case]
pos1, pos2 = 0, 0
for pos0 in range(len(data[id0]) ):
x = data[id0][pos0]
pos1 = LowerBound(x, id1, pos1)
if pos1 < len(data[id1]):
y = data[id1][pos1]
pos2 = LowerBound(y, id2, pos2)
if pos2 < len(data[id2]):
z = data[id2][pos2]
if dist[case] >= z-x:
dist[case] = z-x
pos[case] = [pos0, pos1, pos2]
else:
break
else:
break
min_case = 0
for case in range( 1, len(test_cases) ):
if dist[case] < dist[min_case]:
min_case = case
#=============================
# display data and output
print data[0];
print data[1];
print data[2];
q0, q1, q2 = test_cases[min_case]
pos0, pos1, pos2 = pos[min_case]
print 'the minimal distance is ', dist[min_case]
print 'queue ', q0, ' at ', pos0, ' with value ', data[q0][pos0];
print 'queue ', q1, ' at ', pos1, ' with value ', data[q1][pos1];
print 'queue ', q2, ' at ', pos2, ' with value ', data[q2][pos2];

distance

【在 d****o 的大作中提到】

: You are given with three sorted arrays ( in ascending order), you are
: required to find a triplet ( one element from each array) such that distance
: is minimum.
: Distance is defined like this :
: If a[i], b[j] and c[k] are three elements then
: distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
: Please give a solution in O(n) time complexity

z*c2011-09-20 07:09

31 楼

可以把三个数组merge到一个大数组中，同时要保留element from where
用三个变量记录most recent element from each array 从大数组的开始遍历，
假设当前数来自数组A，那么找到它到most recent B and most recent C的距离。然后
更新most recent A。
不知这样对不？

l*y2011-09-20 07:09

32 楼

像楼主说的，每次把最小的往上移。
用了三个指针，分别指向三个数组，中间会交换指针，min, mid, max，他们分别指向
三个从小到到大排列的数，距离就是 *max -*min.
最后return the minimal distance, the vector d records the three elements
with minimal distance.
请指正，谢谢了！
void swap(vector::iterator &a, vector::iterator &b){
vector::iterator temp;
temp=a;

a=b;
b=temp;
}
int min_dist(vector &a, vector &b, vector &c, vector &d){
vector::iterator min=a.begin(), mid=b.begin(), max=c.begin();
int dist=100000; //Make the initial dist large enough.
for(int i=0; i<3; ++i)
{ d.push_back(0);}

while (min!= a.end() && min!= b.end() && min!=c.end()){
if (*min > *mid) swap(min, mid);
if (*mid > *max) swap(mid, max);
if (*min > *mid) swap(min, mid);
int t=*max - *min;
if (dist > t)

{
dist= t;
d[0]=*min;
d[1]=*mid;
d[2]=*max;

}
++min;

}
return dist;
}

【在 c*****e 的大作中提到】

: 每次总是移a,b,c中最小的一个？

H*12011-09-20 07:09

33 楼

1，10， 40
2， 3， 19
5，80， 90
要找三个数的距离之和最小
答案应该是1,3,5
但这种办法不可能找到啊

one,

【在 d****o 的大作中提到】

: 好像这道题的思路是这样的。（不知道和你的方法是不是最后的结果一样。没有怎么看
: 懂你的方法为什么）
: 假设
: A = {4, 10, 15, 20}
: B = {1, 13, 29}
: C = {5, 14, 28}
: 1. 初始化一个全局最小值minDistance=INT_MAX;当前距离curDistance=0;
: 2. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.(a=1,b=4,c=5)
: 3. 找到最小值a，最开始在B[0],那么我就一直把a往右移，直到a>b (13>4),假设移到

b*u2011-09-20 07:09

34 楼

不是找距离和最小，而是max。 125和135是一样的

【在 H*****1 的大作中提到】

: 1，10， 40
: 2， 3， 19
: 5，80， 90
: 要找三个数的距离之和最小
: 答案应该是1,3,5
: 但这种办法不可能找到啊
:
: one,

b*u2011-09-20 07:09

35 楼

最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。

b*v2011-09-20 07:09

36 楼

1, 2, 5也可以吧

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 H*****1 的大作中提到】

: 1，10， 40
: 2， 3， 19
: 5，80， 90
: 要找三个数的距离之和最小
: 答案应该是1,3,5
: 但这种办法不可能找到啊
:
: one,

z*n2011-09-20 07:09

37 楼

每次把（X,Y，Z）中最小的往上移一位，计算一个min distance，得到一个新的（X，Y
，Z），重复以上步骤，最多一共 3N 次可以完成，O(N)

h*y2011-09-20 07:09

38 楼

这个应该好证明吧？

【在 b***u 的大作中提到】

: 最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。

h*y2011-09-20 07:09

39 楼

每次移动最大的，只会让结果更大
移动中间的，最大的不会变
但是，不知道是否一定是全局最优解
大家能够给个证明么？

【在 h*****y 的大作中提到】

: 这个应该好证明吧？

i*h2011-09-20 07:09

40 楼

这个不就是我前两天说的题么?
改头换面又出来了, 果然经典啊.

p*u2011-09-20 07:09

41 楼

nice code!

【在 x*******5 的大作中提到】

: The code: 欢迎验证
: int Array::Find_value(vector a, vector b, vector c){
: std::sort(a.begin(),a.end());
: std::sort(b.begin(),b.end());
: std::sort(c.begin(),c.end());
: int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
: int l=INT_MAX;
: while(i: l=min(l,max(a[i]-b[j],max(b[j]-c[k],c[k]-a[i])));
: if(a[i]<=b[j]&&a[i]<=c[k]) i++;

x*52011-09-20 07:09

42 楼

证明也许比较难，但是我是这样做的：
/*Description: given three arrays A, B,C, find three indices i,j, k such that
the value l=max((a-b),(b-c), (c-a)) is minimized
Input: vector a, vector b, vector c
Output: void
K.O.: sorting, merge sort variant
*/
int Array::Find_value_brute(vector a, vector b, vector c){
int n=a.size(),m=b.size(),p=c.size(),l=INT_MAX;
for(int i=0;ifor(int j=0;jfor(int k=0;k

int ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=abs(c[k]-a[i]);
l=min(l,max(ta,max(tb,tc)));
}
return l;
}
int Array::Find_value(vector a, vector b, vector c){
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
std::sort(c.begin(),c.end());
int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
int l=INT_MAX;
while(iint ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=abs(c[k]-a[i]);
l=min(l,max(ta,max(tb,tc)));
if(a[i]<=b[j]&&a[i]<=c[k]) i++;
else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
else if(c[k]<=a[i]&&c[k]<=b[j]) k++;
}
return l;
}
提出的方法应该和brute force的结果一样，于是
int count=0;
for(int i=0;i<20000;i++){
vector a=Pearl::generate_int_swap(10,100);
vector b=Pearl::generate_int_knuth(10,200);
vector c=Pearl::generate_int_floyd(10,300);
int t1=Array::Find_value_brute(a,b,c);
int t2=Array::Find_value(a,b,c);
if (t1!=t2)
count++;
}
cout<a,b,c是三个长度为10的随即数组，三个函数是我自己写的随即数生成器（idea来自编
程珠玑，所以namespace取的是Pearl）
多次实验，count都是0

w*y2011-09-20 07:09

43 楼

翻出这倒老题, 看了大家的回复, 都是讲算法没有讲证明的
我理解算法是:
3个数, 找出max/median/min, 这三个数的 distance = max-min
如果要最小化distance, 就把min变大直到min超过median了, 就重新计算distance, 并
更新max/median/min --- 直到min移到结束了

我愚钝, 不会自己证明啊 555555555 这种greedy的方法减少了很多不必要的搜索,
但是怎么证明这个是对的? //汗

l*y2011-09-20 07:09

44 楼

按三路归并的办法，把三个数组并成一个，在这个过程中就找到了所需triplet。
首先设minDistance为MAXINT。归并的过程中，每次选三个数组各自最小元素的最小的
拿出来放入归并好的序列。假设某时刻三个数组的最小元素分别为ai,bj,ck，且ai最小
，我们记录max(|ai-bj|,|ai-ck|)的值。这个值就是在最后归并好的序列中，以ai为最
小数的triplet的Distance（可用反证法证明，因为bj和ck分别是另外两个数组中比ai
大的最小的数，所以再取更大的数Distance一定更大），记为curDistance，然后更新
minDistance如果比它更小（并且记住该minDistance对应的triplet是ai,bj,ck）。
完成归并后，我们就得到了minDistance和所需的那个triplet。

distance

【在 d****o 的大作中提到】

: You are given with three sorted arrays ( in ascending order), you are
: required to find a triplet ( one element from each array) such that distance
: is minimum.
: Distance is defined like this :
: If a[i], b[j] and c[k] are three elements then
: distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
: Please give a solution in O(n) time complexity

f*i2011-09-20 07:09

45 楼

What about the duplicate cases?
{2, 9, 15}
{5, 9, 13}
{7, 19, 21}
After reaching 9,9,7, which "9" entry should be increased?

h*y2011-09-20 07:09

46 楼

留个记号

g*x2011-09-20 07:09

47 楼

Suppose three arrays got merged into one in ascending order, the triplet
with minimum distance must appear as ... Xi, Yj, Zk ... OR ... Xi, Yj, Yj+1,
..., Yj',Zk ... The distance is Zk - Xi.
So one scan/merge on three arrays by ascending order, can detect the triplet
in above patterns and find out the minimum distance for sure.

【在 w***y 的大作中提到】

: 翻出这倒老题, 看了大家的回复, 都是讲算法没有讲证明的
: 我理解算法是:
: 3个数, 找出max/median/min, 这三个数的 distance = max-min
: 如果要最小化distance, 就把min变大直到min超过median了, 就重新计算distance, 并
: 更新max/median/min --- 直到min移到结束了
:
: 我愚钝, 不会自己证明啊 555555555 这种greedy的方法减少了很多不必要的搜索,
: 但是怎么证明这个是对的? //汗

t*j2011-09-20 07:09

48 楼

三路归并，然后sliding window，扫描至结束。

ai

【在 l*y 的大作中提到】

: 按三路归并的办法，把三个数组并成一个，在这个过程中就找到了所需triplet。
: 首先设minDistance为MAXINT。归并的过程中，每次选三个数组各自最小元素的最小的
: 拿出来放入归并好的序列。假设某时刻三个数组的最小元素分别为ai,bj,ck，且ai最小
: ，我们记录max(|ai-bj|,|ai-ck|)的值。这个值就是在最后归并好的序列中，以ai为最
: 小数的triplet的Distance（可用反证法证明，因为bj和ck分别是另外两个数组中比ai
: 大的最小的数，所以再取更大的数Distance一定更大），记为curDistance，然后更新
: minDistance如果比它更小（并且记住该minDistance对应的triplet是ai,bj,ck）。
: 完成归并后，我们就得到了minDistance和所需的那个triplet。
:
: distance

c*m2011-09-20 07:09

49 楼

这样不行吧，sliding window是固定size=3么？

【在 t*****j 的大作中提到】

: 三路归并，然后sliding window，扫描至结束。
:
: ai