Koios1143的筆記

TOJ 47

發表於 更新於 分類於

TOJ 47

題目

https://toj.tfcis.org/oj/pro/47/

給一串長度為 $n$ 的序列，有 $m$ 筆詢問

對於每一筆詢問

  • 若 $q$ 存在於序列當中則直接輸出 $q$
  • 若 $q$ 介於序列中的某兩連續元素之間，輸出那兩個元素
  • 若 $q$ 小於序列的第零項(也就是 $q$ 小於序列中的所有元素)，則輸出no 以及第零個元素
  • 若 $q$ 大於序列的最後項(也就是 $q$ 大於序列中的所有元素)，則輸出最後項以及 no

想法

首先因為我們的答案可能藉在某兩個連續的元素之間，所以我們應該要嘗試讓序列是有嚴格遞增或是嚴格遞減的性質

所以我們第一步是要先將序列排序

排序過後，我們可以先處理兩個包含 no 的特例

直接判斷 $q$ 和 arr[0] 以及 arr[n-1] 的關係即可

如果 $q < arr[0]$ ，就輸出 no arr[0]

如果 $q > arr[n-1]$ ，就輸出 arr[n-1] no

接下來就是要來找我們的詢問 $q$ 是在序列中的哪個位置

我們可以用二分搜來序列當中第一個 $\geq q$ 的元素位置 (也就是 lower_bound)

接下來，如果找到的 $res$ 在 $arr$ 上就是 $q$ 那就直接輸出

否則直接輸出 arr[res-1] arr[res]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, q, res, arr[1000010];
int Lower_bound(int l, int r, int p){
	while(l!=r){
		// >= p 的要留下，其他的篩掉
		int mid = (l+r)/2;
		if(arr[mid] < p) l = mid+1;
		else r = mid;
	}
	return l;
}
int main(){
	cin>>n;
	for(int i=0 ; i<n ; i++){
		cin>>arr[i];
	}
	
	sort(arr, arr+n);
	
	cin>>m;
	for(int i=0 ; i<m ; i++){
		cin>>q;
		// 先判斷包含 no 的情況
		if(arr[0] > q) cout<<"no "<<arr[0]<<"\n";
		else if(arr[n-1] < q) cout<<arr[n-1]<<" no\n";
		// 再來判斷 q 必定包含在序列當中的狀況
		else{
			res = Lower_bound(0, n, q);
			if(arr[res] == q) cout<<q<<"\n";
			else cout<<arr[res-1]<<" "<<arr[res]<<"\n";
		}
	}
	return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(n)$

排序時間複雜度為 $O(nlogn)$

每筆詢問進行二分搜的時間複雜度為 $O(logn)$

總時間複雜度為 $O(n + (m+n)log)$