# APCS實作題2026年3月中高級第2題：觀光旅遊

> 日期：2026年3月11日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=s180)

## 題目

### 問題描述

某旅行社正準備接待 $n$ 個不同的旅行團。第 $i$ 個旅行團預計在第 $t_i$ 天抵達觀光景點。

當地共有 $m$ 個表演，第 $j$ 個表演的演出期間是從第 $s_j$ 天到第 $e_j$ 天（包含首尾兩天），且每天都會演出一場。為了確保遊客體驗，景點保證：**在同一天內，任何兩個不同的表演演出時間都不會重疊**。這意味著如果一個旅行團在第 $t_i$ 天在場，且當天有多個表演正在展演期內，該團可以看完當天所有的表演。

如果第 $i$ 團旅行團的抵達日期 $t_i$ 滿足 $s_j \leq t_i \leq e_j$，則該團可以觀看第 $j$ 個表演。旅行社想要計算這 $n$ 團旅行團總共最多可以看多少場表演（即：將每個旅行團能看到的表演數量加總）。

例如有 $3$ 組旅行團抵達時間為 $7, 5, 10$，總共有 $5$ 種表演時間分別為 $(2, 5), (3, 9), (7, 8), (4, 6), (5, 6)$。
第 $1$ 組旅行團可以看編號為 $2, 3$ 共 $2$ 場表演。
第 $2$ 組旅行團可以看編號為 $1, 2, 4, 5$ 共 $4$ 場表演。
第 $3$ 組旅行團沒有任何表演可以看。
這 $4$ 組旅行團總共可以看 $6$ 場表演。
<br />

### 輸入說明

第一行包含兩個整數 $n$ 和 $m$ ($1 \leq n, m \leq 10^5$)，分別代表旅行團的數量與表演的數量。

第二行包含 $n$ 個整數 $t_1, t_2, \dots, t_n$ ($1 \leq t_i \leq 10^8$)，代表每個旅行團抵達的日期。

接下來的 $m$ 行，每行包含兩個整數 $s_j$ 和 $e_j$ ($1 \leq s_j \leq e_j \leq 10^8$)，代表第 $j$ 個表演的開始與結束日期。

配分
- 40分：$1 \leq n, m \leq 10^3$
- 60分：無限制。

<br />

### 輸出格式

對於每個詢問，輸出一行包含一個整數 $k$，即滿足條件的分割點索引。
<br />

### 範例輸入1

3 5
7 5 10
2 5
3 9
7 8
4 6
5 6

### 範例輸出1

6

### 範例輸入2

12 15
11 4 2 13 6 7 1 19 9 8 20 16
5 21
1 16
11 29
11 20
3 29
18 26
15 26
1 19
22 23
2 8
7 11
2 10
22 29
10 28
18 27

### 範例輸出2

77

<br />

## Python 程式碼

只要抵達日期 $t_i$ 滿足 $s_j \leq t_i \leq e_j$ 就可以看第 $j$ 場表演，因此我將 $s_j$、$t_i$、$e_j$ 後面分別接上 $0, 1, 2$，將 $(s_j, 0), (t_i, 1), (e_j, 2)$ 存入串列 $time$ 再由小到大排序。接下來用變數 $curr$ 儲存目前的表演數量，用 $ans$ 儲存可以看到的表演數量；依序讀取 $time$ 的資料 $t, op$，如果 $op = 1$ 則 $curr$ 加 1；如果 $op = 2$ 則 $ans$ 加 $curr$；如果 $op = 3$ 則 $curr$ 減 1。費時最久約為 0.3 s，使用記憶體最多約為 41.6 MB，通過測試。

n, m = map(int, input().split())
time = []  # (start, 1), (end, 3), (arrive, 2)
for a in map(int, input().split()):
    time.append((a, 2))
for _ in range(m):
    start, end = map(int, input().split())
    time.append((start, 1))
    time.append((end, 3))

time.sort()
ans = 0
curr = 0
for t, op in time:
    if op == 1: curr += 1
    elif op == 2: ans += curr
    elif op == 3: curr -= 1
print(ans)

<br /><br />

## C++ 程式碼

費時最久約為 36 ms，使用記憶體最多約為 12.9 MB，通過測試。

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

int main() {
    long n, m;
    scanf("%ld %ld", &n, &m);
    vector<pair<long, long>> time;  // (start, 1), (end, 3), (arrive, 2)
    for(long i=0; i<n; i++) {
        long a; scanf("%ld", &a);
        time.push_back(make_pair(a, 2));
    }
    for(long i=0; i<m; i++) {
        long start, end;
        scanf("%ld %ld", &start, &end);
        time.push_back(make_pair(start, 1));
        time.push_back(make_pair(end, 3));
    }
    sort(time.begin(), time.end());
    long ans = 0, curr = 0;
    for(auto it : time) {
        long op = it.second;
        if (op == 1) curr++;
        else if (op == 2) ans += curr;
        else if (op == 3) curr--;
    }
    printf("%ld\n", ans);
    return 0;
}

<br /><br />

---

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