# 演算法課程題解 - 二分搜尋
# Kattis - Sort of Sorting
## 題目
https://open.kattis.com/problems/sortofsorting
今天有很多字串要做排序，排序的方式是這樣的
要比較兩個字串的大小，我們只需要看這兩個字串的前兩個字元即可
而這兩組的兩個字元所組成的兩組字串比較方式是字典序
如果說這兩組字串的字典序是相同的，那麼就依照原本的順序排即可
:::info
補充: 字典序
字典序指的是依照 `A-Z` 以及 `a-z` 的方式排列，更廣義的來說，你可以參考 ascii table 每個字所對應的數值，我們就是依照這個大小來比較的
在 C++ 當中，我們可以用 `int(c)` 來找到字元 `c` 所對應到的數值
:::
舉例來說，要排序兩個字串 `Poincare` 以及 `Pochhammmer`
因為前兩個字的字典序相同，所以依照原本的順序即可 `Poincare Pochhammmer`
再舉一個例子，要排序兩個字串 `Beethoven` 以及 `Bach`
的一個字元的字典序相同，而第二個字的字典序 `a` 比 `e` 小，所以放在前面 `Bach Beethoven`
## 想法 By Koios1143
其實這個排序方式就是所謂的 stable sort， 在 C++ 當中已經有這個函數可以使用
不同的是排序的方式，所以我們要另外寫 compare 函數
比較的方式在前面也有提到就不贅述，詳細可以直接看 code 當中的 `cmp()`
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string arr[205];
bool cmp(string p, string q){
// 先比較第一個字元
if(int(p[0]) != int(q[0])){
return int(p[0]) < int(q[0]);
}
// 再比較第二個字元
else{
if(int(p[1]) != int(q[1])){
return int(p[1]) < int(q[1]);
}
}
// false 表示字典序 p>=q
return false;
}
int main(){
int n;
bool out=false;
while(cin>>n && n){
// 在輸出之間需要有換行
if(out) cout<<"\n";
else out = true;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
stable_sort(arr, arr+n, cmp);
for(int i=0 ; i<n ; i++){
cout<<arr[i]<<"\n";
}
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度 $O(n)$
每筆測資排序時間複雜度 $O(nlogn)$
每筆測資輸出時間複雜度 $O(n)$
每筆測茲的總時間複雜度約為 $O(n + nlogn)$
# Kattis - Sideways Sorting
## 題目
https://open.kattis.com/problems/sidewayssorting
一般來說我們排序字串都是由左到右，但是本題要我們由上到下來看
輸入第一行包含兩個正整數 $r, c$，表示 row 與 column
接下來有 $r$ 行，每行 $c$ 個字元
最後輸出垂直方向由上到下的**穩定排序**
並且排序過程當中忽略大小寫
舉例來說
```
oTs
nwi
eox
```
從垂直的方向來看，我們會得到三個字串
```
one
Two
six
```
接下來排序這幾個字串
```
one
six
Two
```
最後排回原本的橫向
```
osT
niw
exo
```
## 想法 By Koios
因為排序的方向是垂直的，我們可以直接以垂直的方式儲存這些字串即可
接下來穩定排序過後在改變輸出的方向即可
至於排序的部分，我們可以先把所有要比較的字串先都轉換成小寫之後再來比較大小
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string arr[20];
bool cmp(string p, string q){
// 先轉換成小寫
for(int i=0 ; i<p.size() ; i++){
p[i] = tolower(p[i]);
}
for(int i=0 ; i<q.size() ; i++){
q[i] = tolower(q[i]);
}
// 接下來再比較大小
if(p != q) return p<q;
return false;
}
int main(){
int r,c;
char tmp;
bool out=false;
while(cin>>r>>c && (r!=0 && c!=0)){
// 輸出之間需要有換行
if(out) cout<<"\n";
else out=true;
// 初始化所有字串
for(int i=0 ; i<c ; i++){
arr[i] = "";
}
for(int i=0 ; i<r ; i++){
for(int j=0 ; j<c ; j++){
// 把字串串起來
cin>>tmp;
arr[j]+=tmp;
}
}
stable_sort(arr, arr+c, cmp);
for(int i=0 ; i<r ; i++){
for(int j=0 ; j<c ; j++){
// 記得輸出方向是相反
cout<<arr[j][i];
}
cout<<"\n";
}
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(rc)$
每筆測資初始化時間複雜度為 $O(rc)$
每筆測資排序時間複雜度為 $O((len(p) + len(q)) \times nlogn)$
每筆測資輸出時間複雜度為 $O(rc)$
每筆測資總時間複雜度約為 $O(rc + nlogn)$ ($len(p) + len(q)$ 很小，可以忽視)
# TOJ 47
## 題目
https://toj.tfcis.org/oj/pro/47/
給一串長度為 $n$ 的序列，有 $m$ 筆詢問
對於每一筆詢問
- 若 $q$ 存在於序列當中則直接輸出 $q$
- 若 $q$ 介於序列中的某兩連續元素之間，輸出那兩個元素
- 若 $q$ 小於序列的第零項(也就是 $q$ 小於序列中的所有元素)，則輸出`no` 以及第零個元素
- 若 $q$ 大於序列的最後項(也就是 $q$ 大於序列中的所有元素)，則輸出最後項以及 `no`
## 想法 By Koios
首先因為我們的答案可能藉在某兩個連續的元素之間，所以我們應該要嘗試讓序列是有**嚴格遞增**或是**嚴格遞減**的性質
所以我們第一步是要先將序列排序
排序過後，我們可以先處理兩個包含 `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]`
### 程式碼
```cpp=
//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;
}
```
:::info
實際上我們可以不用自行實作 lower_bound
在 C++ 可以直接 `#include<algorithm>`，裡面就有 `lower_bound` 以及 `upper_bound` 可以直接使用，使用方式如下
```cpp=
#include<iostream>
#include<algorithm>
using namespace std;
int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int main(){
cout<<*lower_bound(arr, arr+10, 5)<<'\n'; // 輸出 5
return 0;
}
```
`lower_bound` 以及 `upper_bound` 回傳的都是指標，所以要用 `*` 取出值
如果想要得到元素是位在 $arr$ 中的哪個位置，可以用 `lower_bound(arr, arr+10, 5)-arr` 取得
:::
### 時間複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
每筆詢問進行二分搜的時間複雜度為 $O(logn)$
總時間複雜度為 $O(n + (m+n)log)$
# TOJ 468
## 題目
https://toj.tfcis.org/oj/pro/468/
輸入包含 $n$ 個元素的序列，接下來 $m$ 筆詢問
每筆詢問包含兩個正整數 $p, q$，求在序列當中有多少百分比的元素介於 $p$ 至 $q$
小數精確至小數點後第 $k$ 位
## 想法 By Koios
先對序列做排序
接下來題目要問的是有多少元素介於 $p, q$ 之間
如果我們能找到第一個 $\geq p$ 的元素位置以及第一個 $> q$ 的元素位置，那麼這兩個元素之間的個數就是我們的答案
要找第一個 $\geq p$ 的元素位置就等同於找 lower_bound
要找第一個 $> q$ 的元素位置就等同於找 upper_bound
### 程式碼
```cpp=
//By Koios1143
#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){
// >= p 的要留下，其他的篩掉
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){
// > p 的要留下，其他的篩掉
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;
}
```
:::info
跟上一題一樣的，實際上沒有必要自己實作 `lower_bound` 以及 `upper_bound`
可以直接引用 C++ `algorithm` 裡的函數即可
:::
### 時間複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
找 lower_bound 以及 upper_bound 總時間複雜度為 $O(2logn)$
總時間複雜度為 $O(n + nlogn)$
# UVa 907
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?907
有一群人要去旅行，旅行的路線必須要經過 $n$ 個暫停點休息
已經知道包含起點以及終點這 $n+1$ 條邊之間的距離是多少
請問這一趟旅程當中一天最多走多長的距離，才可以在 $k$ 個晚上 (也就是 $k+1$ 天) 內到從起點達終點?
## 想法
如果說一天走 $m$ 個距離可以在 $k+1$ 天內到達，那麼 $m+1$ 也一定可以
所以我們發現到了行走距離是具有單調性的
有了單調性，要我們搜尋最佳答案就可以使用二分搜
我們可以二分搜一天最少所需的行走距離，如果說距離 $m$ 不能在 $k+1$ 天內走到，那就更新左界至 $m+1$，否則更新右界至 $m$
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, k, Min, Max, ans, arr[610];
int search(int l, int r, int p){
while(l!=r){
int mid = (l+r)/2;
int days = 0, dis = 0;
for(int i=0 ; i<n+1 ; i++){
if(arr[i] + dis > mid){
// 如果過去的距離加上當前的距離會超過，就表示需要多一天來走
// 並且要從當前距離開始繼續計算
days++;
dis = arr[i];
}
else{
dis += arr[i];
}
}
// 最後檢查有沒有剩下的路段
if(dis > 0) days++;
// 記得 p 指的是多少個晚上，等同於天數-1
if(days-1 > p) l = mid+1;
else r = mid;
}
return l;
}
int main(){
while(cin>>n>>k){
Min = Max = 0;
for(int i=0 ; i<n+1 ; i++){
cin>>arr[i];
// 最短的單次距離至少是長度的最大值
Min = max(Min, arr[i]);
// 最長的單次距離是一次走到終點
Max += arr[i];
}
cout<<search(Min, Max, k)<<"\n";
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(n+1)$
二分搜的範圍最差會是總距離，也就是 $\sum_{i=0}^{n+1}{arr[i]}$
搜尋時間複雜度為 $O(log{\sum_{i=0}^{n+1}{arr[i]}})$
總時間複雜度約為 $O(n + log{\sum_{i=0}^{n+1}{arr[i]}})$
# ZJ c575
## 題目
https://zerojudge.tw/ShowProblem?problemid=c575
有一條路上有 $n$ 個電信的服務點 $p_i$，現在我們要裝設最多 $k$ 個基地台，讓這 $n$ 個電信服務點都能接收到訊號
基地台可以放在座標點上的任意位置，並且有一個直徑為 $R$ 的訊號涵蓋範圍
給定這 $n$ 個點的座標，是否能找到一個最小 $R$，使得所有服務點都能接收到訊號
## 想法 By Koios
如果說直徑 $R$ 可以在 $k$ 個基地台內涵蓋整個區域，那麼 $R+1$ 也一定可以
所以我們觀察到 $R$ 具有單調性，並且基地台是可以任意擺放的，哪麼要找 $R$ 的最小值就可以用二分搜來求解
我們可以二分搜 $R$ 的大小
從 $p_0$ 開始每次增加 $R$，把涵蓋在 $p_0$ ~ $p_0 + R$ 的服務點移除
接著從沒被移除掉的點中找到最左端的服務點繼續檢查
最後如果需要用的基地台數量大於 $k$ 就更新左界成 $R+1$，否則更新右界成 $R$
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
long long n, k, Min, Max, arr[50010];
int search(long long l, long long r, long long p){
while(l!=r){
long long mid = (l+r)/2;
long long dis = 0, cnt = 0;
for(long long i=0, now=0 ; i<n ; ){
// 把涵蓋在 arr[i] ~ arr[i]+mid 的服務點移除(忽略)
while(arr[now] <= arr[i]+mid && now<n)
now++;
cnt++;
i = now;
}
// 最後檢查是否還有沒加上的基地台
if(dis > 0) cnt++;
if(cnt > p) l = mid+1;
else r = mid;
}
return l;
}
int main(){
while(cin>>n>>k){
Min = Max = 0;
for(long long i=0 ; i<n ; i++){
cin>>arr[i];
}
// 題目並無保證座標已經過排序
sort(arr, arr+n);
// 不需要特別去找最小直徑，那需要額外 O(n) 的時間
Min = 1, Max = (arr[n-1]-arr[0])/k+1;
cout<<search(Min, Max, k)<<"\n";
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(n)$
排序時間複雜度為 $O(nlogn)$
二分搜的值為 $D = max(arr) - min(arr) + 1$
搜尋時間複雜度為 $O(D)$
本題的 $D$ 不超過 $10^6$
總時間複雜度約為 $O(n + nlogn + log(D)$
# TOJ 556
## 題目
https://toj.tfcis.org/oj/pro/556/
有 $N$ 項工作，為了好好管理進度，我們把每一份工作都分成了 $K$ 份
對於第 $i$ 項工作每天可以完成 $a_i$ 份，並且每天都會做每一項工作
因為怕工作會做不完，我們有 $M$ 筆經費可以將工作外包
每一經費對於第 $i$ 項工作可以將其中的 $b_i$ 份工作外包，並且不需考慮外包的作業時間
請問在最佳分配經費的情況下，最少可以在幾天之內完成 $N$ 份工作
$$
1 \leq N \leq 10^5\\
1 \leq K \leq 10^9\\
0 \leq M \leq 10^9\\
1 \leq a_i \leq 10^9\\
1 \leq b_i \leq 10^9
$$
## 想法 By Koios
如果說 $X$ 天可以把工作處理完成，那麼 $X+1$ 天也一定可以
發現到天數是具有單調性的，那麼要求最小的天數就可以用二分搜來完成
二分搜最小所需要的天數 $X$，確認 $X$ 是否可行來調整左界與右界
那麼要怎麼確認 $X$ 天能不能完成呢?
我們可以把每一項工作都先減去 $X$ 天自己做可以完成的工作量
那麼剩下的所有工作就必須要外包才能完成了
最後計算需要外包的數量，就可以判斷是否可以在 $X$ 天完成了!
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
long long n, k, m, L=0, R=1e9+10, A[100005], B[100005], tmp[100005];
long long search(long long l, long long r, long long p){
while(l<r){
long long mid = (l+r)/2, cnt=0;
for(long long i=0 ; i<n ; i++){
// 先扣除 mid 天可以自己完成的工作量
tmp[i] = k - A[i]*mid;
if(tmp[i] > 0){
// 剩下的全部外包
cnt += tmp[i]/B[i];
if(tmp[i] % B[i] > 0) cnt++;
}
}
if(cnt > p) l = mid + 1;
else r = mid;
}
return l;
}
int main(){
cin>>n>>k>>m;
for(long long i=0 ; i<n ; i++){
cin>>A[i];
R = min(R, A[i]);
}
for(long long i=0 ; i<n ; i++){
cin>>B[i];
}
// 最大工作天數為 (工作份數K / 一天處理最小的工作量)
R = k/R + 1;
cout<<search(L, R, m)<<"\n";
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(n)$
二分搜的右界為 $R' = k / min(R) + 1$
搜尋時間複雜度為 $O(nlog{R'})$
總時間複雜度為 $O(n + nlog{R'})$
# UVa 10282
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10282
題目會先給你每個英文字對應到的外國文字，這群對應的字保證是一對一，形成一個字典
接下來會有多筆詢問，輸入一個外國文字，輸出相對應的英文字，如果不存在則輸出 `eh`
## 想法 By Koios
這題可以直接用 map 對應，但是這裡我們用二分搜來實作看看
首先先把字典建立好，可以用一個 struct 來建立每個英文字對應到的外國字，接下來排序，方便我們查詢
最後用二分搜就可以了
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<sstream>
#include<algorithm>
using namespace std;
int i=0, res, res2;
string s, key, value, q;
struct word{
string key;
string value;
};
word dict[100010];
bool cmp(word p, word q){
if(p.value != q.value) return p.value < q.value;
return false;
}
int search(int l, int r, string p){
while(l!=r){
int mid = (l+r)/2;
if(dict[mid].value == p) return mid;
if(dict[mid].value < p) l = mid+1;
else r=mid;
}
return -1;
}
int main(){
while(getline(cin, s) && s!=""){
// 因為輸入是用換行間格，一次讀取一整行比較好判斷
// 接下來用 stringstream 分割字串
stringstream ss;
ss<<s;
ss>>key>>value;
dict[i].key = key;
dict[i].value = value;
i++;
}
sort(&dict[0], &dict[i], cmp);
while(cin>>q){
res = search(0, i, q);
if(res == -1) cout<<"eh\n";
else cout<<dict[res].key<<"\n";
}
return 0;
}
```
### 時間複雜度分析
假設有 $N$ 筆輸入以及 $Q$ 筆詢問
輸入時間複雜度為 $O(N)$
排序時間複雜度為 $O(NlogN)$
搜尋時間複雜度為 $O(QlogN)$
總時間複雜度為 $O(N + (N+Q)logN)$
# UVa 10341
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10341
今天有一個算式 $p * e^{-x} + q * sin(x) + r * cos(x) + s * tan(x) + t * x^{2} + u = 0$
已知 $0 \leq x \leq 1$，給定 $p, q, r, s, t, u$，求 $x$
$0 \leq p, r \leq 20 \\
-20 \leq q, s, t \leq 0$
## 想法 By Koios
首先先來觀察一下算式，將算式中的每個部份拆分出來
我們只討論 $x$ 所在的的範圍 $0 \leq x \leq 1$
- $e^{-x}$ 為遞減函數
- $sin(x)$ 為遞增函數
- $cos(x)$ 為遞減函數
- $tan(x)$ 為遞增函數
- $x^{2}$ 為遞增函數
接下來把係數也考慮進去
- $p * e^{-x}$ 為遞減函數
- $q * sin(x)$ 為遞減函數
- $r * cos(x)$ 為遞減函數
- $s * tan(x)$ 為遞減函數
- $t * x^{2}$ 為遞減函數
由此可知， $p * e^{-x} + q * sin(x) + r * cos(x) + s * tan(x) + t * x^{2} + u$ 是**遞減函數**
令這個函數為 $f(x)$
知道這個函數是呈現遞減的狀態，我們要求其解就想到利用二分搜
透過二分搜，我們可以枚舉 $x$，並且有三種情況
- $f(x) = 0$
x 就是答案
- $f(x) > 0$
因為函數是遞減，當答案大於 0 則應該要調整邊界**向右移動**
- $f(x) < 0$
因為函數是遞減，當答案大於 0 則應該要調整邊界**向左移動**
但是程式會有浮點數的誤差存在，所以很難判斷到底應不應該繼續往下尋找答案
但是因為 $f(x)$ 是連續函數，我們可以用勘根定理找到是否存在解，只要除去不存在解的情況，我們就可以放心地往下繼續找答案
除去無解的情況，接下來找答案就很快了
但是浮點數誤差一定要小心處理
:::info
$f(x)$ 當中有很多數學函數，在 C++ 當中可以直接 `#include<math.h>`
其中 $sin(x), cos(x), tan(x)$ 都可以直接使用
$e^{x}$ 則可以用 `exp(x)` 表示
:::
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<iomanip>
#include<math.h>
using namespace std;
double p, q, r, s, t, u, esp=1e-9;
double abs2(double x){
// 因為沒有針對 double 的 abs 存在，自己寫一個
return (x<0 ? -x : x);
}
double ans(double x){
// 直接回傳 x 帶入算式的結果
return p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;
}
double search(double l, double r){
double mid, ret=1;
// 只要答案還在誤差範圍內就放心搜尋
while(abs2(ret) > esp){
mid = (l+r)/2.0;
ret = ans(mid);
if(ret < 0) r = mid;
else l = mid;
}
return mid;
}
int main(){
while(cin>>p>>q>>r>>s>>t>>u){
// 當左右邊界的值帶入後答案相乘大於 0 則不存在解 (勘根定理)
if(ans(1) * ans(0) > 0) cout<<"No solution\n";
else{
double x = search(0, 1+esp);
cout<<fixed<<setprecision(4)<<x<<"\n";
}
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(1)$
每筆測資找答案的時間複雜度為 $O(logN)$ $N = 10^{9}$
每筆測資總時間複雜度約為 $O(logN)$
# TOJ 55
## 題目
https://toj.tfcis.org/oj/pro/55/
輸入 $n$ 個數字，接下來有 $m$ 筆詢問，想知道詢問的數字 $q$ 在序列當中出現的次數
## 想法 By Koios
直接計算 upper_bound ($>q$ 的第一個位置) - lower_bound ($\leq q$ 的第一個位置)
因為這一題的輸入數量有點大，需要加上輸入優化
:::info
加上了輸入優化後，就不可以將 c 和 c++ 的 IO 語法混用，要注意這一點
可以參考 https://hackmd.io/@wiwiho/CPN-io-optimization
:::
### 程式碼
```cpp=
//By Koios1143
#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)$
# UVa 10110
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10110
在一條走廊上有編號 $1$~$n$ 的電燈泡
有個人在這條走廊上來回走 $n$ 趟，第 $i$ 次出發會將編號為 $i$ 的倍數的電燈泡開關轉換一次(也就是 `開 -> 關` `關 -> 開`)，而在走回來不會做任何事
請問來回走完 $n$ 趟之後，第 $n$ 顆電燈泡是亮的還是暗的? (一開始所有電燈泡都是關的)
## 想法 By Koios
如果第 $n$ 個電燈泡是關的，那麼他一定被操作了 $2k$ 次 ($k \in \mathscr{R}$)
反過來說，如果第 $n$ 個電燈泡是開的，那麼他一定被操作了 $2k-1$ 次 ($k \in \mathscr{R}$)
那何時電燈泡會被操作呢?
只有在他的因數出現的時候會被操作到
那麼如果某數字有奇數個因數，則最後會是開的，反之是關的
任何數字 $p$ 的因數 $q$ 都會有相對應的數字 $r$ 使得 $p = qr$，並且 $r$ 也是 $p$ 的因數
如果說因數是奇數，那就表示最中間的因數 $q$ 找到相對應的數字也是 $q$，使得 $p = q*q$
發現到，當因數個數為奇數，也就是 $p$ 是**完全平方數**的時候第 $n$ 個燈泡會是亮的，反之是暗的
那麼，我們只需要做開根號的動作，去看看開根號後的值平方以及原本的數字是否相同即可
不過這裡要練習二分搜，所以就二分搜開根號吧
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
long long n, tmp;
void search(long long l, long long r, long long p){
long long mid, res;
while(l!=r){
mid = (l+r)/2;
res = mid*mid;
if(res == p){
cout<<"yes\n";
return;
}
if(res < p) l = mid+1;
else r = mid;
}
cout<<"no\n";
return;
}
int main(){
while(cin>>n && n){
search(0, n+1, n);
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(1)$
每筆測資找到答案的時間複雜度為 $O(logn)$
每筆測資總時間複雜度為 $O(logn)$
# UVa 10474
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10474
每一筆測資有 $n$ 筆資料以及 $q$ 筆詢問
要求資料排序過後，每筆詢問的數字在資料當中第一次出現的位置，從一開始數
## 想法 By Koios
要找排序後的位置，當然先排序好
在排序完成後，要找第一次出現的位置，那就直接帶入 lower_bound 的概念即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, q, res, arr[10010], Case=1;
int main(){
while(cin>>n>>q && (n!=0 && q!=0)){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
sort(arr, arr+n);
cout<<"CASE# "<<Case++<<":\n";
for(int i=0, m ; i<q ; i++){
cin>>m;
res = lower_bound(arr, arr+n, m)-arr;
if(arr[res] == m){
cout<<m<<" found at "<<res+1<<"\n";
}
else{
cout<<m<<" not found\n";
}
}
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資找搜尋時間複雜度為 $O(logn)$
每筆測資總時間複雜度為 $O(n + qlogn)$
# UVa 10530
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10530
現在正在玩猜數字的遊戲，對方會告訴你你猜的數字太高或是太低，但是我們懷疑對方會說謊
假設當我們猜到正確數字時對方並不會說謊，給定每回合猜數字的結果，請幫忙判斷對方是否有說謊
猜數字的範圍在 $1$~$10$ 之間
## 想法 By Koios
給定一個數字，對方回覆太大(`too high`)，那麼如果沒說謊，我們的數字應該比他還小，那麼我們只需要紀錄 `too high` 當中最小的數字即可
反過來說，對方回覆太大(`too low`)，那麼如果沒說謊，我們的數字應該比他還大，那麼我們只需要紀錄 `too low` 當中最大的數字即可
如果我們猜到的數字介在 `too high` 以及 `too low` 之間，那就表示對方沒有說謊
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, Upper_bound = 10, Lower_bound = 1;
string s;
int main(){
while(cin>>n && n){
getchar();
getline(cin, s);
if(s == "too high"){
// 數字最大是 n-1
Upper_bound = min(Upper_bound, n-1);
}
else if(s == "too low"){
// 數字最小是 n+1
Lower_bound = max(Lower_bound, n+1);
}
else if(s == "right on"){
if(n >= Lower_bound && n <= Upper_bound){
cout<<"Stan may be honest\n";
}
else{
cout<<"Stan is dishonest\n";
}
Upper_bound = 10, Lower_bound = 1;
}
}
return 0;
}
```
###### tags: `SCIST 演算法 題解`
Sign in with Wallet
Connect another wallet