一、问题描述
黑白连线 | ||
---|---|---|
Time Limit: 1000 MS | Memory Limit: 1000 KB |
Description
给定直线上2n个点的序列P[1,2,… ,2n],每个点P[i]要么是白点要么是黑点,其中共有n个白点和n个黑点,
相邻两个点之间距离均为1,请设计一个算法将每个白点与一黑点相连,使得连线的总长度最小。例如,图中有
4个白点和4个黑点,以图中方式相连,连线总长度为1+1+1+5=8。
Input
第一行输入m表示有m组测试. 每组测试首先输入n(n<=10000),接下来输入2n个0或者1, 分别表示白色或者
黑色, 其中0和1的个数分别为n个.
Output
对每组测试数据输出最小总连线长度.
Sample Input
2
4
1 1 0 1 0 0 0 1
4
0 0 1 0 1 1 1 0
Sample Output
8
8
二、思路分析
该题应用贪心法进行求解:
思路1(比较简单):
每遇到一个未被连接点,就向后寻找第一个(最近的)不同的点。
这个思路时间复杂度较高、空间复杂度较低。
思路2:
(1)维护一个黑点栈和白点栈;
(2)按顺序遍历每一个点,如果遇到一个白点,就查看当前黑点栈是否为空,非空的话就将将该白点与黑点栈顶黑点连接(因为栈是先入先出,所以栈顶黑点就是离该白点最近的未连接的黑点);遇到黑点也做类似的操作。
这个思路时间复杂度较低、空间复杂度较高。
文章来源:https://www.toymoban.com/news/detail-446017.html
三、代码示例
思路一的逻辑较简单,因此在此只给出思路二的代码示例:文章来源地址https://www.toymoban.com/news/detail-446017.html
#include <iostream>
#include <stack>
using namespace std;
int main(int argc, const char * argv[]) {
// 共m组测试数据
int m;
cin >> m;
while((m--) > 0) {
// 输入黑白点的数量n,即共有2*n个点
int n;
cin >> n;
// 创建点数组points并输入各个点
int* points = new int[2*n];
for(int pi = 0; pi < 2 * n; ++pi) {
cin >> points[pi];
}
// 创建黑白点栈
stack<int> whitePoints;
stack<int> blackPoints;
// 初始化结果
int result = 0;
//依次遍历每一个点
for(int pi = 0; pi < 2 * n; ++pi) {
// 如果是白色的点
if(points[pi] == 0) {
// 如果黑点栈中没有黑点,就将这个白点入栈。
if(blackPoints.empty()) {
whitePoints.push(pi);
}
// 如果黑点栈中有点,则取出栈顶元素,将二者进行配对
else {
result += (pi - blackPoints.top());
blackPoints.pop();
}
}
// 如果是黑色的点
else {
// 如果白点栈中没有白点,就将这个黑点入栈。
if(whitePoints.empty()) {
blackPoints.push(pi);
}
// 如果白点栈中有点,则取出栈顶元素,将二者进行配对
else {
result += (pi - whitePoints.top());
whitePoints.pop();
}
}
}
// 输出结果
cout << result << endl;
delete [] points;
}
return 0;
}
到了这里,关于贪心法——黑白连线问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!