2022.05.06 PS 일지

공항

문제 링크
각 비행기를 도착하는 순서대로 남은 조건을 만족하는 게이트에 도킹시키는 문제이다. 물론 도킹 수가 최대가 되는 것이 목적이다.

풀이

게이트의 선택지는 $1\cdots g_i$이다. $g_i$가 큰 비행기들은 굳이 작은 게이트를 택함으로써 $g_i$가 작은 비행기들의 자리를 뺏을 이유가 없다.

따라서 $g_i$ 이하 중 가장 큰 게이트를 택하는 그리디 전략이 성립할 수 있다.

근데... 증명은... 어케하지..?

Overplanting

문제 링크
jinhan814님 코드가 깔끔하길래 본계정으로 다시 풀었다.

풀이.

직사각형의 합집합의 넓이를 구하는 유형인데, $N$이 작다.

그냥 좌표압축 느낌으로 풀이하면 되는데, 구현이 중요하다.

코드

query, update을 밖으로 빼니 편하게 구현이 가능했다.

#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;
using ll = long long;

int n;
vector<tuple<int,int,int,int>> vert;
map<int,ll> swl;
ll answer, pre, prv;
vector<ll> len;

ll query(int x) {
    ll r = 0; int i = 0;
    for (auto [k,v] : swl) {
        if (v > 0) r += len[i];
        ++i;
    }
    r *= x-pre, pre = x;
    return r;
}

void update(int l, int r, int d) {
    for (auto &[k,v] : swl)
        if (l < k and k <= r) v += d;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    REP(i,1,n) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        vert.push_back({y1,y2,x1,+1});
        vert.push_back({y1,y2,x2,-1});
        swl[y1] = 0, swl[y2] = 0;
    }
    for (auto [k,_] : swl)
        len.push_back(k-prv), prv = k;

    sort(begin(vert),end(vert),[](auto &x, auto &y) {
        return get<2>(x) < get<2>(y);
    });
    for (auto [y1,y2,x,d] : vert)
        answer += query(x), update(y2,y1,d);
    cout << answer;
}