演算法課程題解 - 二分搜尋

Kattis - Sort of Sorting

題目

https://open.kattis.com/problems/sortofsorting

今天有很多字串要做排序，排序的方式是這樣的
要比較兩個字串的大小，我們只需要看這兩個字串的前兩個字元即可
而這兩組的兩個字元所組成的兩組字串比較方式是字典序
如果說這兩組字串的字典序是相同的，那麼就依照原本的順序排即可

補充: 字典序

字典序指的是依照 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()

程式碼

//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

因為排序的方向是垂直的，我們可以直接以垂直的方式儲存這些字串即可
接下來穩定排序過後在改變輸出的方向即可
至於排序的部分，我們可以先把所有要比較的字串先都轉換成小寫之後再來比較大小

程式碼

//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$ 是在序列中的哪個位置
我們可以用二分搜來序列當中第一個

$\ge q$ 的元素位置 (也就是 lower_bound)
接下來，如果找到的

$res$ 在

$arr$ 上就是

$q$ 那就直接輸出
否則直接輸出 arr[res-1] arr[res]

程式碼

//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;
}

實際上我們可以不用自行實作 lower_bound
在 C++ 可以直接 #include<algorithm>，裡面就有 lower_bound 以及 upper_bound 可以直接使用，使用方式如下

#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$ 之間
如果我們能找到第一個

$\ge p$ 的元素位置以及第一個

$>q$ 的元素位置，那麼這兩個元素之間的個數就是我們的答案

要找第一個

$\ge p$ 的元素位置就等同於找 lower_bound
要找第一個

$>q$ 的元素位置就等同於找 upper_bound

程式碼

//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;
}

跟上一題一樣的，實際上沒有必要自己實作 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$

程式碼

//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$

程式碼

//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$ 份工作

$$\begin{gathered} 1\le N\le {10}^5 \\ 1\le K\le {10}^9 \\ 0\le M\le {10}^9 \\ 1\le a_i\le {10}^9 \\ 1\le b_i\le {10}^9 \end{gathered}$$

想法 By Koios

如果說

$X$ 天可以把工作處理完成，那麼

$X+1$ 天也一定可以
發現到天數是具有單調性的，那麼要求最小的天數就可以用二分搜來完成

二分搜最小所需要的天數

$X$，確認

$X$ 是否可行來調整左界與右界
那麼要怎麼確認

$X$ 天能不能完成呢?
我們可以把每一項工作都先減去

$X$ 天自己做可以完成的工作量
那麼剩下的所有工作就必須要外包才能完成了
最後計算需要外包的數量，就可以判斷是否可以在

$X$ 天完成了!

程式碼

//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^{\prime }=k/min(R)+1$
搜尋時間複雜度為

$O(nlog{R}^{\prime })$
總時間複雜度為

$O(n+nlog{R}^{\prime })$

UVa 10282

題目

http://domen111.github.io/UVa-Easy-Viewer/?10282

題目會先給你每個英文字對應到的外國文字，這群對應的字保證是一對一，形成一個字典
接下來會有多筆詢問，輸入一個外國文字，輸出相對應的英文字，如果不存在則輸出 eh

想法 By Koios

這題可以直接用 map 對應，但是這裡我們用二分搜來實作看看
首先先把字典建立好，可以用一個 struct 來建立每個英文字對應到的外國字，接下來排序，方便我們查詢
最後用二分搜就可以了

程式碼

//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\ast e^{-x}+q\ast sin(x)+r\ast cos(x)+s\ast tan(x)+t\ast x^2+u=0$
已知

$0\le x\le 1$，給定

$p,q,r,s,t,u$，求

$x$

$$\begin{gathered} 0\le p,r\le 20 \\ -20\le q,s,t\le 0 \end{gathered}$$

想法 By Koios

首先先來觀察一下算式，將算式中的每個部份拆分出來
我們只討論

$x$ 所在的的範圍

$0\le x\le 1$

• $e^{-x}$ 為遞減函數
• $sin(x)$ 為遞增函數
• $cos(x)$ 為遞減函數
• $tan(x)$ 為遞增函數
• $x^2$ 為遞增函數

接下來把係數也考慮進去

• $p\ast e^{-x}$ 為遞減函數
• $q\ast sin(x)$ 為遞減函數
• $r\ast cos(x)$ 為遞減函數
• $s\ast tan(x)$ 為遞減函數
• $t\ast x^2$ 為遞減函數

由此可知，

$p\ast e^{-x}+q\ast sin(x)+r\ast cos(x)+s\ast tan(x)+t\ast x^2+u$ 是遞減函數
令這個函數為

$f(x)$

知道這個函數是呈現遞減的狀態，我們要求其解就想到利用二分搜
透過二分搜，我們可以枚舉

$x$，並且有三種情況

• $f(x)=0$
  x 就是答案
• $f(x)>0$
  因為函數是遞減，當答案大於 0 則應該要調整邊界向右移動
• $f(x)<0$
  因為函數是遞減，當答案大於 0 則應該要調整邊界向左移動

但是程式會有浮點數的誤差存在，所以很難判斷到底應不應該繼續往下尋找答案
但是因為

$f(x)$ 是連續函數，我們可以用勘根定理找到是否存在解，只要除去不存在解的情況，我們就可以放心地往下繼續找答案

除去無解的情況，接下來找答案就很快了
但是浮點數誤差一定要小心處理

$f(x)$ 當中有很多數學函數，在 C++ 當中可以直接 #include<math.h>
其中

$sin(x),cos(x),tan(x)$ 都可以直接使用

$e^x$ 則可以用 exp(x) 表示

程式碼

//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 (

$\le q$ 的第一個位置)
因為這一題的輸入數量有點大，需要加上輸入優化

加上了輸入優化後，就不可以將 c 和 c++ 的 IO 語法混用，要注意這一點
可以參考 https://hackmd.io/@wiwiho/CPN-io-optimization

程式碼

//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 \mathcal{R}$)
反過來說，如果第

$n$ 個電燈泡是開的，那麼他一定被操作了

$2k-1$ 次 (

$k\in \mathcal{R}$)

那何時電燈泡會被操作呢?
只有在他的因數出現的時候會被操作到
那麼如果某數字有奇數個因數，則最後會是開的，反之是關的

任何數字

$p$ 的因數

$q$ 都會有相對應的數字

$r$ 使得

$p=qr$，並且

$r$ 也是

$p$ 的因數
如果說因數是奇數，那就表示最中間的因數

$q$ 找到相對應的數字也是

$q$，使得

$p=q\ast q$
發現到，當因數個數為奇數，也就是

$p$ 是完全平方數的時候第

$n$ 個燈泡會是亮的，反之是暗的

那麼，我們只需要做開根號的動作，去看看開根號後的值平方以及原本的數字是否相同即可
不過這裡要練習二分搜，所以就二分搜開根號吧

程式碼

//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 的概念即可

程式碼

//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 之間，那就表示對方沒有說謊

程式碼

//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 演算法 題解