[COCI] 백준 2836 - 수상 택시

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

관찰

사람을 어떻게 태우던지 목적지에 도착해야 되므로 최소 M만큼의 거리를 이동한다.

 

어차피 배도 M으로 향해야 하므로 M방향으로 가는 사람들은 무시하고 역방향으로 가는 사람만 고려하면 된다.

 

역방향으로 가는 사람들은 어떻게 되는걸까? 한번 지나간 곳을 또 지나가는 것은 최적해에 도달할 수 없음을 떠올릴 수 있고 그러면 사람이 오르내리는 사건이 발생하는 최대 구간을 만드는 것을 생각할 수 있다.

 

최적해에 관한 예시로 5와 7 지점에서 역방향으로 가려는 손님이 있는데 5를 태운 다음 7을 태우지 않고 뒤로 돌아간다면 7을 태우기 위해 다시 그만큼 거리를 이동해야 하므로 최적해가 아님을 알 수 있다.

 

따라서 스위핑을 통해 역방향 노선을 적절히 합쳐주고 sum(역방향으로 움직이는 거리 * 2)(왕복해야 되니까)를 M에 더해준 값이 정답이 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int n, m;

vector<pii> sweep(vector<pii> &v)
{
    vector<pii> res;

    int l = v[0].first, r = v[0].second;
    
    for (int i = 1; i < v.size(); ++i)
    {
        if (l <= v[i].first && v[i].first <= r)
            r = max(r, v[i].second);
        else
        {
            res.push_back({l, r});
            l = v[i].first, r = v[i].second;
        }
    }
    res.push_back({l, r});
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    vector<pii> v2;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        if (a > b)
            v2.push_back({b, a});
    }

    sort(v2.begin(), v2.end());
    vector<pii> v4 = sweep(v2);

    ll res = 0;

    for (int i = 0; i < v4.size(); ++i)
        res += (v4[i].second - v4[i].first) * 2;
    cout << (ll)m + res;
}