TOJ 55
題目
https://toj.tfcis.org/oj/pro/55/
輸入 $n$ 個數字，接下來有 $m$ 筆詢問，想知道詢問的數字 $q$ 在序列當中出現的次數
想法
直接計算 upper_bound ($>q$ 的第一個位置) - lower_bound ($\leq q$ 的第一個位置)
因為這一題的輸入數量有點大，需要加上輸入優化
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, arr[1000010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
cin>>m;
for(int i=0, q ; i<m ; i++){
cin>>q;
cout<<upper_bound(arr, arr+n, q) - lower_bound(arr, arr+n, q)<<"\n";
}
return 0;
}
|
時間複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
二分搜時間複雜度為 $O(logn)$
總時間複雜度約為 $O(n + nlogn)$