一、问题描述
给出一个距离的集合D， 求出在x轴，存在哪些点能够组合成这样的距离集合； 假设第一个点在0处：path[1] = 0; 最后一个点是距离集合中最大的距离：path[N] = max(D); 使用堆或是红黑树存放距离集合D；
二、具体的代码如下
#include <iostream>
#include <vector>
#include <set>
using namespace std
;
bool
place(vector
<int>& path
, multiset
<int>& D
, int N
, int left
, int right
) {
bool found
= false
;
if (D
.empty())
return true
;
multiset
<int>::iterator iter
= D
.end();
--iter
;
path
[right
] = *iter
;
int i
, j
;
for (i
= 1; i
< left
; i
++) {
if ((iter
= D
.find(path
[right
] - path
[i
])) != D
.end())
D
.erase(iter
);
else
{
for (int k
= i
- 1; k
> 0; k
--)
D
.insert(path
[right
] - path
[i
]);
break;
}
}
if (i
== left
) {
for (i
= right
+ 1; i
<= N
; i
++) {
if ((iter
= D
.find(path
[i
] - path
[right
])) != D
.end())
D
.erase(iter
);
else {
for (int k
= 1; k
< left
; k
++)
D
.insert(path
[right
] - path
[k
]);
for (int k
= i
- 1; k
> right
; k
--)
D
.insert(path
[k
] - path
[right
]);
break;
}
}
if (i
== N
+ 1) {
found
= place(path
, D
, N
, left
, right
- 1);
if (!found
) {
for (i
= 1; i
< left
; i
++)
D
.insert(path
[right
] - path
[i
]);
for (i
= right
+ 1; i
<= N
; i
++)
D
.insert(path
[i
] - path
[right
]);
}
else
return true
;
}
path
[left
] = path
[N
] - path
[right
];
for (i
= 1; i
< left
; i
++) {
if ((iter
= D
.find(path
[left
] - path
[i
])) != D
.end())
D
.erase(iter
);
else {
for (int k
= i
- 1; k
> 0; k
--)
D
.insert(path
[left
] - path
[k
]);
break;
}
}
if (i
== left
) {
for (i
= right
+ 1; i
<= N
; i
++) {
if ((iter
= D
.find(path
[i
] - path
[left
])) != D
.end())
D
.erase(iter
);
else {
for (int k
= 1; k
< left
; k
++)
D
.insert(path
[left
] - path
[k
]);
for (int k
= i
- 1; k
> right
; k
--)
D
.insert(path
[k
] - path
[left
]);
break;
}
}
if (i
== N
+ 1) {
found
= place(path
, D
, N
, left
+ 1, right
);
if (!found
) {
for (i
= 1; i
< left
; i
++)
D
.insert(path
[left
] - path
[i
]);
for (i
= right
+ 1; i
<= N
; i
++)
D
.insert(path
[i
] - path
[left
]);
}
else
return true
;
}
}
return false
;
}
}
bool
turnpike(vector
<int>& path
, multiset
<int> &D
, int N
) {
path
[1] = 0;
multiset
<int>::iterator iter
= D
.end();
path
[N
] = *(--iter
);
--iter
;
D
.erase(path
[N
]);
path
[N
- 1] = *iter
;
D
.erase(path
[N
- 1]);
if ((iter
= D
.find(path
[N
] - path
[N
- 1])) != D
.end()) {
D
.erase(iter
);
return place(path
, D
, N
, 2, N
- 2);
}
return 0;
}
int main()
{
multiset
<int> D
;
int arr
[] = { 1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10 };
int len
= sizeof(arr
) / sizeof(arr
[0]);
for (int i
= 0; i
< len
; i
++)
D
.insert(arr
[i
]);
int N
= 6;
vector
<int> path(N
+1);
turnpike(path
, D
, N
);
for (auto x
: path
)
cout
<< x
<< endl
;
return 0;
}
