백준 2836 수상 택시 C++

https://www.acmicpc.net/problem/2836

2836번: 수상 택시

수상 택시로 사람들을 태워다니면서 가는 최소 거리를 구하는 문제입니다.

태우는 사람에 대한 조건은 따로 없으니 순방향으로 가는 사람은 가는 길에 내려준다고 생각하면 총 M 만큼 이동합니다.

역방향으로 가는 사람은 스위핑 알고리즘을 이용한 선분 길이 구하는 것과 동일하게 계산하면서 x 2 만큼 길이를 구하면 됩니다.

(역방향이므로 갔다가 다시 원래 방향으로 가야 함)

 

코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
long long M;
long long result;
vector<pair<long long, long long>> people;

// 원래 방향대로 가는 사람은 가는 길에 태워다 주면 됨
// 역방향 이동하는 애들만 대상으로 선분 길이 구하는 
// 스위핑 동일하게 적용해서 * 2 하면 됨 (역방향이므로)

void init()
{
  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    long long from, to;
    cin >> from >> to;
    if(from < to)
      continue;
    people.push_back({to, from});
  }

  sort(people.begin(), people.end());
}

void calc()
{
  // 스위핑으로 선분 길이 구하는 거랑 동일 (*2 만 차이)
  long long start = -1;
  long long last = -1;

  for(auto p : people) {
    // 선분 끊어짐
    if(last < p.first) {
      result += (last - start);
      start = p.first;
    }
    // 선분 갱신
    if(last < p.second) {
      last = p.second;
    }
  }

  // 남은 길이
  result += (last - start);
  result *= 2;
  result += M; // 원래 가야하는 길이
  cout << result;
}

int main() {
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  init();
  calc();
}