一条直线上N个线段所覆盖的总长度

转自http://blog.csdn.net/bxyill/article/details/8962832

问题描述:

现有一直线,从原点到无穷大。

这条直线上有N个线段。线段可能相交。

问,N个线段总共覆盖了多长?(重复覆盖的地区只计算一次)

================================================

解题思路:

可以将每个线段拆分成“单位1”

遍历所有线段,使用一个数组记录每个线段所走过的“单位1”

最后统计数组中被走过的中“单位1”的个数,即是所有线段覆盖的总长度了。

这里有个问题?数组的大小如何确定?

数组的大小应该是所有线段中最大的端点坐标。

 ===============================================

顺便想到一个问题。

给出若干个线段。求一共有几个“连通域”。就是将能合并的线段 合并成一个线段。

最后能合并出几个来?

利用上面的思想。非常简单。

只需遍历单位数组的时候做个开始和结尾的记录就行了。

程序实现如下。

===============================================

//此题要求
//求出一条直线上所有线段所覆盖的全程长度是多少。
//重叠的地方只计算一次。
//================================
//本算法的思想是,将每个线段进行像素化,
//添加到一个单位数组c[N]中
//遍历c数组判断哪些单位被覆盖到了,
//在count计数一下就知道一共覆盖了多少路程。
//真是巧妙啊。
//==============================
#include <iostream>
using namespace std;
const int N = 10000;
//线段结构体
struct Segment
{
    int start;
    int end;
};
//
int coverage(Segment *segments, int n)
{
    bool c[N]={false};//每个“单位1”是否被覆盖到

    int start=0;
    int end = 0;
    //遍历n个线段
    for(int i = 0; i < n; i++)
    {
        for(int j = segments[i].start; j < segments[i].end; j++)
        {
            c[j] = true;
        }
        //寻找最右端
        if(segments[i].end > end)
        {
            end = segments[i].end;
        }
        //寻找最左端
        if(segments[i].start < start)
        {
            start = segments[i].start;
        }
    }
    //从最左端开始到最右端。遍历单位数组C
    int count = 0;
    for(int i= start; i < end; i++)
    {
        if(c[i])
        {
            int s=i;
            while(c[i])
            {
                count++;
                i++;
            }
            int e=i;
            cout << "["<<s<<","<<e<<"]"<<endl;
        }
    }
    return count;
};

int main()
{
    Segment s1;
    s1.start = 1;
    s1.end = 3;

    Segment s2;
    s2.start = 2;
    s2.end = 6;

    Segment s3;
    s3.start = 11;
    s3.end = 12;

    Segment s4;
    s4.start = 10;
    s4.end = 13;
    Segment ss[] = {s1,s2,s3,s4};
    cout << "归并后"<<endl;
    cout <<"被覆盖总长度:" <<coverage(ss, sizeof(ss)/sizeof(ss[0]))<<endl;
}

输出结果如下:

归并后 [1,6] [10,13]

被覆盖总长度 8

请按任意键继续. . .

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python3

习题4:变量和命名

"_"下划线这个符号在变量里通常被用作假象的空格,用来隔开单词,切记千万不要用"-"这个符号来连接单词

592
来自专栏大数据风控

Python中字段抽取、字段拆分、记录抽取

1、字段抽取 字段抽取是根据已知列数据的开始和结束位置,抽取出新的列 字段截取函数:slice(start,stop) 注意:和数据结构的访问方式一样,开始位置...

3218
来自专栏技术碎碎念

递归与分治之快速排序

分治法就是把一个大问题分解为多个类型相同的子问题,最后把这些子问题的解合并起来就是问题的解。 快速排序(Quicksort)是对冒泡排序的一种改进,采用了分治的...

3056
来自专栏Bingo的深度学习杂货店

Q155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element ...

2836
来自专栏糊一笑

关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是: 写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ...

57110
来自专栏JavaEdge

设计模式实战 - 解释器模式(Interpreter Pattern)

● 公式可以运行时编辑,并且符合正常算术书写方式,例如a+b-c ● 高扩展性,未来增加指数、开方、极限、求导等运算符号时较少改动 ● 效率可以不用考虑,晚...

1162
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

2037
来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

1513
来自专栏前端儿

A+B Problem(V)

做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

851
来自专栏tkokof 的技术,小趣及杂念

sizeof 知多少?

稍熟悉C/C++的朋友,对于sizeof肯定不陌生,通过他我们可以知晓某个类型或者实例的内存大小(以字节计),但是如果深入一下sizeof计算的细节,想来大部分...

750

扫码关注云+社区

领取腾讯云代金券