问题描述:

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

这条直线上有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

请按任意键继续. . .

 

 

技术
©2019-2020 Toolsou All rights reserved,
数字滚动抽奖小程序VaR - 风险价值 - 蒙特卡罗法 - Python百度网盘偷偷更新,终于实现免费不限速了! Chrome OS,对程序员和Windows意味着什么?,互联网营销华为Mate 40 Pro+ 5G曝光:徕卡电影镜头、陶瓷机身Qt学习2——.pro文件和.h文件介绍python:将一个文件转换为二进制文件(binary)第十一届蓝桥杯C/C++ 大学 B 组大赛软件类省赛网站手机号码抓取方式蚂蚁集团香港IPO获得中国证监会批准