贪心法——黑白连线问题

这篇具有很好参考价值的文章主要介绍了贪心法——黑白连线问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、问题描述

黑白连线
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

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 如何让心情保持平静?100多条禅修心法

    静的层次和阶段 静首先是不要去争,没有任何争的心,没有任何杂念心。静有几个层次阶段: ⒈. 自己的心情相对于自己平静,是平静的第一个阶段。 ⒉. 第二个平静的阶段是:别人觉得你很静,自己也很静,这个相对比较真实了。 有的人一点都不静,说“我挺静的呀,”

    2023年04月19日
    浏览(52)
  • 专访同程王晓波:探一座古城,寻一位技术大侠的内功心法

    俗话说“上有天堂,下有苏杭”,苏州作为一座有着数千年历史的闻名古城,有着和北上广深等一线城市所不同的生活节奏,互联网业态在这座城里也正在勃兴。在这里,有着一位圈内苏州互联网的代表人物:同程旅行出行事业群 CTO、腾讯云 TVP 王晓波老师,他为何选择了苏

    2024年02月06日
    浏览(36)
  • 背包问题(贪心)& 二维01背包问题 Java

    题目描述 有n件物品和一个最大承重为w 的背包。第i件物品的重量是weight[i],每件只能用一次,求装入背包的最多物品数量。 题目分析 因为我们 只要求装入物品的数量 ,所以 装重的显然没有装轻的划算 。 因此将 数组weight[i]按从小到大排序 , 依次选择每个物品 ,直到装不

    2024年01月17日
    浏览(42)
  • 贪心算法(区间问题)

    有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气

    2024年03月11日
    浏览(72)
  • 贪心法解决背包问题

    贪心法的基本概念 (1)贪心法要解决的问题是这样的一类问题,有n个输入,问题的解由这n个输入的某个子集组成,同时要求这个子集必须满足某些事先给定的条件,这些必须满足的条件称为约束条件。 (2)满足约束条件的子集,被称为可行解。 (3)为了衡量可行解的优

    2024年02月10日
    浏览(31)
  • 打水问题(贪心算法)

    题目:有n个人排队到r个水龙头去打水,他们装满水桶的时间t1、t2………tn为整数且各不相等,应如何安排他们的打水顺序才能使他们总共花费的时间最少?通过键盘输入排队打水的人数以及每人打水的时间和水龙头数,使用贪心算法求出所有人完成打水总共花费的时间的最

    2024年04月28日
    浏览(53)
  • 会场安排问题(贪心)

    2024年03月26日
    浏览(40)
  • 【算法-贪心】分数背包问题

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(43)
  • 贪心算法——背包问题

    14天阅读挑战赛 目录 1.题目描述      2.问题分析 3.算法设计 4.C++程序

    2023年04月18日
    浏览(78)
  • 带有期限的作业排序问题(贪心)

    转载【算法设计】带有期限的作业排序(贪心算法)_带时限的作业排序贪心算法-CSDN博客 主要是给自己加注释   已知:         n个作业,每个作业都有一个截止期限di,当且仅当作业i在它的期限截止以前被完成时,可获得pi的效益。 求:         可行解集合J   测试

    2024年02月05日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包