はまやんはまやんはまやん

hamayanhamayan's blog

Two Elevators [CSAcademy #60 B]

https://csacademy.com/contest/round-60/task/two-elevators/

N階建ての建物に2つのエレベーターがある。
i番目のエレベーターは最初E[i]階にいる。
各エレベーターは1階に下ろすかN階まで上げるかの2択を選択できる。
N人がエレベーターを待っている。
i番目の人はA[i]階からB[i]階へ移動したい。
2つのエレベーターの2択を適切に選択して、エレベーターによってちゃんと移動できる人数を最大化せよ。

解法

2つのエレベーターがあるが、下の階で止まっているエレベーターが上に、上の階で止まっているエレベーターが下に移動するのが最適。
あとは、そのエレベーターに乗って移動が完了するかを確かめて答え。

int N, E1, E2, A[101010], B[101010];
int C, D;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> E1 >> E2;
    rep(i, 0, N) cin >> A[i] >> B[i];

    int ans = 0;

    // 小さい方はあげる
    C = min(E1, E2);
    rep(i, 0, N) if (C <= A[i] and A[i] < B[i]) ans++;

    // 大きい方は下げる
    D = max(E1, E2);
    rep(i, 0, N) if (A[i] <= D and A[i] > B[i]) ans++;

    cout << ans << endl;
}