TOJ 468
題目
https://toj.tfcis.org/oj/pro/468/
輸入包含 $n$ 個元素的序列，接下來 $m$ 筆詢問
每筆詢問包含兩個正整數 $p, q$，求在序列當中有多少百分比的元素介於 $p$ 至 $q$
小數精確至小數點後第 $k$ 位
想法
先對序列做排序
接下來題目要問的是有多少元素介於 $p, q$ 之間
如果我們能找到第一個 $\geq p$ 的元素位置以及第一個 $> q$ 的元素位置，那麼這兩個元素之間的個數就是我們的答案
要找第一個 $\geq p$ 的元素位置就等同於找 lower_bound
要找第一個 $> q$ 的元素位置就等同於找 upper_bound
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
38
39
|
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int n,k,m,l,r,arr[100010];
int Lower_bound(int l, int r, int q){
while(l!=r){
int mid = (l+r)/2;
if(arr[mid] < q) l = mid+1;
else r = mid;
}
return l;
}
int Upper_bound(int l, int r, int q){
while(l!=r){
int mid = (l+r)/2;
if(arr[mid] <= q) l = mid+1;
else r = mid;
}
return l;
}
int main(){
cin>>n>>k;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
cin>>m;
for(int i=0 ; i<m ; i++){
cin>>l>>r;
if(l>r) swap(l, r);
cout<<fixed<<setprecision(k)<<(double)((Upper_bound(0, n, r)) - (Lower_bound(0, n, l)))*100.0/n<<"%\n";
}
return 0;
}
|
時間複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
找 lower_bound 以及 upper_bound 總時間複雜度為 $O(2logn)$
總時間複雜度為 $O(n + nlogn)$