(2836) 수상 택시

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

단계별로 풀어보기

49단계(스위핑) 2번째

 

 

 

0번 집에서 M번 집으로 가는 길은 원래 상근이의 경로이므로 타는 위치보다 목적지가 큰 손님은 이동 거리에 영향을 주지 않는다.

타는 위치보다 목적지가 작은 손님은 그만큼 뒤로 돌아갔다가 다시 돌아와야 하므로 거리의 두배만큼 이동 거리가 증가한다.

이때 경로가 겹치면 손님을 동시에 운반할 수 있으므로, 돌아가는 거리의 최소값은 해당하는 손님들의 경로를 선분으로 생각했을 때 선분의 거리의 합과 같다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<pair<int,int>> v;
  
  while(n--){
    int a, b;
    
    cin >> a >> b;
    
    if(a>b)  v.push_back({b, a});
  }
  
  sort(v.begin(), v.end());
  
  int left= 0, right= 0, len= 0;
  
  for(auto line:v){
    if(line.first<=right){
      right= max(right, line.second);
    }else{
      len+= right-left;
      
      left= line.first;
      right= line.second;
    }
  }
  len+= right-left;
  
  cout << (long)m+2*len;
  
  return 0;
}