[백준 2836] 수상 택시 (C++)

2836번: 수상 택시

 

그리디인줄 알고 삽질을 오래 했다.

 

스위핑 문제였다.

 

시간이 녹았다

하지만 스위핑을 제대로 되새길 수 있었다!

 

 

역방향 이동거리 * 2

 == 초록색으로 표시된 거리 * 2

 

-> 되돌아 가서 승객을 내려주기 + 되돌아 가기 전 위치로 복귀

ANSWER : M + 위 값들의 합

 

스위핑 문제임을 파악하고 좌표의 left, right 값을 잘 설정해주자.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
typedef long long ll;
#define pii pair<ll, ll>

// typedef pair<int, int> pii;

using namespace std;

int N, M;
vector<pii> arr;

void input(){
    cin >> N >> M;
    int s, d;
    for(int i = 0; i < N; i++){
        cin >> s >> d;
        if(s > d) arr.push_back({d, s});
    }
    
    sort(arr.begin(), arr.end());
}

void solve(){
    ll move = M;
    
    int nidx = 0;
    int length = arr.size();
    
    ll left = 0;
    ll right = 0;
    for(int i = 0; i < arr.size(); i++){
        if(arr[i].first > right){
            move += (2 * (right - left));
            left = arr[i].first;
            right = arr[i].second;
        }
        else{
            right = max(right, arr[i].second);
        }
    }
    move += (2 * (right - left));
    
    cout << move;
}

int main(){
    fastio
    input();
    solve();
    
    return 0;
}