# APCS實作題2021年1月第4題：飛黃騰達

> 日期：2024年8月10日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f608)

## 題目

### 問題描述

飛黃是一種生物，活在二維座標平面上。

有隻特別的飛黃一開始在座標 $(0, 0)$ 的位置，而且你知道它只會往右上方移動，也就是移動的時只可以走到 $x$ 座標跟 $y$ 座標都不比原本小的位置。

現在座標平面的第一象限上有 $n$ 個位置有果實，給定這 $n$ 個果實的座標，你想要知道這隻特別的飛黃最多可以吃到幾個果實。它必須移動到果實所在的座標才可以吃到果實。

<br />

### 輸入說明

第一行有一個整數 $n$ 表示果實的數量。

接下來有 $n$ 行，第 $i$ 行的兩個整數 $x, y$ 表示第 $i$ 個果實位於 $(x, y)$ 座標。

保證不會有兩個果實在相同的位置。

配分
- 20分：$1 \leq n \leq 100, ~1 \leq x, y \leq 100$
- 30分：$1 \leq n \leq 1000, ~1 \leq x, y \leq 10^7$
- 50分：$1 \leq n \leq 200000, ~1 \leq x, y \leq 10^7$

<br />

### 輸出格式

輸出一個數字表示最多可以吃到多少果實。
<br />

### 範例輸入

3
1 1
2 5
3 2

### 範例輸出

2

<br /><br />

## Python 程式碼

假設目現所在的位置為 $(x, y)$，下一個果實的位置為 $(x_n, y_n)$，當 $x_n \geq x$ 且 $y_n \geq y$ 時，吃到的果實數量最大值才會增加。因此在第7或8行先將 fruit 依照果實 $x$ 座標由小到大排序，再從 fruit 依序讀取果實的 $y$ 座標，將 $y$ 由小到大插入另一個串列 st，最後 st 的長度就是答案。

費時最久約為 1.2 s，使用記憶體最多約為 32.6 MB，通過測試。

from bisect import bisect_right  # 二分搜尋法

n = int(input())  # 讀取數量 n
#fruit = []  # 儲存果實位置的串列
#for _ in range(n):  # 讀取 n 行資料，轉成二個一組的整數數組再加到 fruit
#    fruit.append(tuple(map(int, input().split())))
#fruit.sort()  # 依照果實 x 座標由小到大排序
fruit = sorted([tuple(map(int, input().split())) for _ in range(n)])  # 效果與第4 ~ 7行相同

st = []  # 果實 y 座標要遞增
for _, y in fruit:  # 依序由 fruit 讀取資料
    if not st or y >= st[-1]: st.append(y)  # 如果 st 是空的或 y 大於等於 st[-1]，找到新的果實，加到 st
    else: st[bisect_right(st, y)] = y  # 否則用 bisect_right 找到於 st 中插入 y 的右側位置，重設值為 y

print(len(st))  # st 的長度就是答案

<br /><br />

## C++ 程式碼

費時最久約為 0.4 s，使用記憶體最多約為 3.5 MB，通過測試。

#include <iostream>
#include <vector>
#include <utility>  // for pair
#include <algorithm>  // for upper_bound
using namespace std;

int main() {
    int n; cin >> n;  // 讀取數量 n
    vector<pair<int, int>> fruit (n, {0, 0});  // 儲存果實位置的陣列
    for(int i=0; i<n; i++) cin >> fruit[i].first >> fruit[i].second;  // 讀取 n 行資料，組成 pair，加到 fruit
    sort(fruit.begin(), fruit.end());  // 依照果實 x 座標由小到大排序
    vector<int> st;  // 果實 y 座標要遞增
    for(auto f : fruit) {  // 依序由 fruit 讀取資料
        if (st.empty() || f.second >= st.back()) st.push_back(f.second);  // 如果 st 是空的或 y 大於等於 st.back()，找到新的果實，加到 st
        else st[upper_bound(st.begin(), st.end(), f.second) - st.begin()] = f.second;  // 否則用 upper_bound 找到於 st 中插入 y 的右側位置，重設值為 y
    }
    cout << st.size() << "\n";  // st 的長度就是答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`