第 04 篇、二分搜 - 進階程式設計 - 多元選修 (高中)

# 課堂練習

# d732: 二分搜尋法

給你一個嚴格遞增的數列，求數列中是否存在一個值與 X 相等？
若有，則輸出該值位置。否則，輸出 0。

因為測資很龐大，所以，不推薦使用線性搜 $O(n)$ 的方式。
又因為序列已經是嚴格遞增的，所以，可以使用二分搜 $O(log_2n)$ 的方式進行搜索。

	#include <iostream>
	using namespace std;

	int main()
	{
	int n,k,x,a[100005];
	while(cin >> n >> k){
	for(int i=1;i<=n;i++)
	cin >> a[i];

	while(k--){
	cin >> x;
	int L = 1,R = n+1;
	int m;
	while(L<=R){
	m = (L + R) / 2;
	if(a[m] == x){
	cout<<m<<endl; break;
	}
	else if (a[m] > x) R = m-1;
	else L = m+1;
	}
	if (L > R)
	cout << 0 << endl;
	}
	}
	return 0;
	}

# f815: TOI_y21m4_a01 遊戲升等

要將 n 個士兵升等，每人升 x 等需 $x^2$ 金幣，現有 c 枚金幣，問全體最少可到幾等？

我們可以透過先假設一個結果，再判斷該結果是否為最佳，
假設錢的總數足夠達到該結果，就將結果往上調一等，
若不足夠，則往下調整一等，直到最終結果是符合結果中的最大值。

但是，依序的搜索對於這題而言太過緩慢，又因為調整的結果情況為一次一次的，類似於查找已排序序列的結果
因此，我們這題可以透過對答案二分搜的方式，將答案逼近到我們想要的目標結果。

(這題的程式碼以左閉右開的形式撰寫)

	#include <iostream>
	using namespace std;
	#define int long long

	int lv[20005],n;
	int gold(int m){ // 計算到等級 m 需要的金幣
	int sum=0;
	for(int i=0;i<n;i++)
	if (lv[i]<m) // 如果士兵等級 < m
	sum += (lv[i]-m)*(lv[i]-m);
	return sum;
	}


	signed main(){
	int c,L=1,R=20000005,m; // 左閉，右開
	cin >> n >> c;

	for(int i=0;i<n;i++)
	cin >> lv[i];

	while(L<R){
	m = (L+R)/2; // 預期的等級 m
	if (gold(m)>c) // 需要的金幣 > 預算
	R = m; // 調整 R
	else
	L = m+1; // 調整 L
	}

	for(int i=1;i<MAXN;i++){
	if(gold(i)>c){ // 金幣不足
	cout<< i-1 <<endl;
	}
	}

	cout << R-1 << endl;
	return 0;
	}

# 延伸練習

# c575: APCS 2017-0304-4 基地台

某電信公司負責其中 N 個服務點，這 N 個服務點位在一條筆直的大道上，它們的位置 (座標) 係以與該大道一端的距離 P [i] 來表示，其中 i=0~N-1。由於設備訂製與維護的因素，每個基地台的服務範圍必須都一樣，當基地台架設後，與此基地台距離不超過 R (稱為基地台的半徑) 的服務點都可以使用無線網路服務，也就是說每一個基地台可以服務的範圍是 D=2R (稱為基地台的直徑)。現在電信公司想要計算，如果要架設 K 個基地台，那麼基地台的最小直徑是多少才能使每個服務點都可以得到服務。
基地台架設的地點不一定要在服務點上，最佳的架設地點也不唯一，但本題只需要求最小直徑即可。

可用二分搜尋的觀點。因為基地台直徑的答案一定介於 1~(最遠服務點 - 最近服務點)。
先假設可能答案為最大最小值中間，測試 k 個基地台可否覆蓋所有服務點，不行則調整基地台直徑，以二分搜尋法找出答案。
(直接對答案進行二分搜尋)

	#include<bits/stdc++.h>
	using namespace std;

	int service, bases, places[50000], lower, upper, middle;

	bool Feasible(int diameter) {
	int counts = 0, bound, i = 0;
	for(;;) {
	bound = places[i] + diameter, ++counts;
	if (counts > bases)
	return false;
	if (places[service - 1] <= bound)
	return true;
	while (places[i] <= bound) {
	++i;
	if (i == service)
	return true;
	}
	}
	}

	int main() {
	cin.sync_with_stdio(false), cin.tie(NULL);
	cin >> service >> bases;
	for (int i = 0; i < service; ++i)
	cin >> places[i];
	sort(places, places + service);
	lower = 1, upper = places[service - 1] - places[0] + 1;
	while (upper - lower >= 1) {
	middle = (lower + upper) >> 1;
	if (Feasible(middle))
	upper = middle;
	else
	lower = middle + 1;
	}
	cout << upper << '\n';
	}

# c904: 天龍國的蜜蘋果

每一顆蘋果的重量 (w) 不一樣，因甜度不同而售價 (v) 也有所不同，今有 N 個蘋果，
試求從中任意取出 K 個蘋果，使其 <單位重量的售價> 為最大。
<單位重量的售價> = <K個蘋果的售價總和> / <K個蘋果的重量總和>

設最大的單位價值爲 x。那麼讓 x 成立的條件爲 $\sum v / \sum w \ge x$ 化簡可以得到
$\sum v / \sum w \ge x \Rightarrow \sum v \ge x \times \sum w =\sum (x \times w) \Rightarrow \sum v-x\times w \ge 0$ ，
所以我們只要讓前 k 個物品都滿足這個條件，那麼此時的 x 就是符合條件的，我們再去找更大的就可以了。

	#include <bits/stdc++.h>
	using namespace std;

	int n,m,weight[1000],value[1000],pick;
	double buffer[1000],sum,lower,upper,mid;

	bool cmp(double a,double b){
	return a>b;
	}

	bool check(double x){
	for(int i=0;i<n;i++)
	buffer[i]=value[i]-x*weight[i];
	sort(buffer,buffer+n,cmp);
	sum=0;
	for(int i=0;i<pick;i++)
	sum+=buffer[i];
	return sum>=0;
	}

	int main(){
	while(cin>>n>>m){
	for(int i=0;i<n;i++)
	cin>>weight[i]>>value[i];
	while(m--){
	cin>>pick,lower=0,upper=1e16;
	for(int i=0;i<70;i++){
	mid=(lower+upper)/2;
	if(check(mid))
	lower=mid;
	else
	upper=mid;
	}
	cout<<fixed<<setprecision(2)<<upper<<endl;
	}
	}
	}

多元選修二分搜