好资源导航 » 文章资讯 » C++ 中的 Klee 算法（线段联合的长度）

C++ 中的 Klee 算法（线段联合的长度）

2023-06-15 10:10:02 72

在本教程中，我们将编写一个程序来查找线段的联合长度。

我们给出了线段的起点和终点，我们需要找到线段的联合长度。

我们将要使用的算法称为克利算法。

让我们看看解决问题的步骤。

使用所有段的坐标初始化数组。

初始化一个称为点的向量，其大小是段数组的两倍。

迭代段数组。

用当前线段的第一个点和false填充索引i*2处的点数组的值。

用当前线段的第二个点和false填充索引i*2+1处的点数组的值。

对点数组进行排序。

使用计数器变量迭代点数组。

如果计数器大于0，则将i和i-1的第一个点添加到结果中。

如果有第二个点，则减少计数器，否则增加它。

返回结果。

示例

让我们看看代码。

#include
using namespace std;
int segmentUnionLength(const vector> &segments) {
   int n = segments.size();
   vector> points(n * 2);
   for (int i = 0; i < n; i++) {
      points[i*2] = make_pair(segments[i].first, false);
      points[i*2 + 1] = make_pair(segments[i].second, true);
   }
   sort(points.begin(), points.end());
   int result = 0, count = 0;
   for (int i = 0; i < n * 2; i++){
      if (count) {
         result += points[i].first - points[i-1].first;
      }
      points[i].second ? count-- : count++;
   }
   return result;
}
int main() {
   vector> segments;
   segments.push_back(make_pair(1, 3));
   segments.push_back(make_pair(2, 7));
   segments.push_back(make_pair(6, 12));
   segments.push_back(make_pair(13, 5));
   cout << segmentUnionLength(segments) << endl;
   return 0;
}

输出结果

如果你运行上面的代码，那么你会得到下面的结果。

结论

如果您对本教程有任何疑问，请在评论部分提及。

返回顶部
514930285
czq8825@qq.com

C++ 中的 Klee 算法（线段联合的长度）

示例

结论

热门推荐

随机推荐