C++의 Klee 알고리즘(선분의 결합 길이)

이 튜토리얼에서는 선분의 ​​합집합 길이를 구하는 프로그램을 작성하겠습니다.

선분의 시작점과 끝점을 지정했으니 선분의 결합 길이를 찾아야 합니다.

우리가 사용할 알고리즘은 klee의 알고리즘이라고 합니다.

이 문제를 해결하는 단계를 살펴보겠습니다.

• 모든 선분의 좌표로 배열을 초기화하세요.
• 선분 배열 크기의 두 배인 포인트라는 벡터를 초기화합니다.
• 선분 배열을 탐색합니다.
  • 현재 선분의 첫 번째 점을 채우고 점 배열의 인덱스 i * 2 위치에 거짓을 입력합니다.
  • 현재 선분의 두 번째 점을 채우고 점 배열의 인덱스 i * 2 + 1 위치에 거짓을 입력합니다.
• 포인트 배열을 정렬하세요.
• count 변수를 사용하여 포인트 배열을 탐색하세요.
  • 카운터가 0보다 큰 경우 i와 i-1의 첫 번째 점을 결과에 추가합니다.
  • 두 번째 포인트가 있으면 카운터를 1씩 감소시키고, 그렇지 않으면 증가시킵니다.
• 결과를 반환합니다.

예제

코드를 살펴보겠습니다.

Demo

#include<bits/stdc++.h>
using namespace std;
int segmentUnionLength(const vector<pair <int,int>> &segments) {
   int n = segments.size();
   vector<pair<int, bool>> 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<pair<int,int>> 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;
}

Output

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

6

결론

튜토리얼 중에 궁금한 점이 있으면 댓글 섹션에 문의하세요.

위 내용은 C++의 Klee 알고리즘(선분의 결합 길이)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!