APCS 110/01 實作題第四題題解 飛黃騰達

2021-01-09 17:00:42 by Akira

題目敘述

你一開始在 (0, 0)，只能往 x 軸正向和 y 軸正向走。有 N 個相異點，問最多能經過幾個點。

即：能從 (a, b) 走到 (c, d) 的條件是 \(a \le c\) 且 \(b \le d\)

輸入格式

\[
\begin{matrix}
N \\
x_1 & y_1 \\
x_2 & y_2 \\
... \\
x_N & y_N
\end{matrix}
\]

\(N \le 200000\)

\(0 \le x, y \le 100000000\)

輸出格式

印出一個數字：最多可以經過幾個點

範例輸入

5
3 2
4 5
2 3
1 3
5 4

範例輸出

3

---

題解

將點按照 x 座標排序後剩下的就是對 y 座標做經典的 LIS (最長遞增子序列) (差別在於不用嚴格遞增)

C++ 參考解答

#include <climits>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int NMAX = 200000;

int N; pair<int, int> P[NMAX];

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) scanf("%d%d", &P[i].first, &P[i].second);
  sort(P, P + N);
  vector<int> A;
  for (int i = 0; i < N; i++) {
    int x = P[i].second;
    int j = upper_bound(A.begin(), A.end(), x) - A.begin();
    if (j >= A.size()) {
      A.push_back(x);
    } else {
      A[j] = x;
    }
  }
  printf("%d\n", (int)A.size());
  return 0;
}

---

[題解] [APCS] [APCS 110/01]