QLU_ACM 淺談二分搜索技術(shù)
by StilllFantasy
二分思想為何物浴捆？
二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是泡态，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列迂卢。
關(guān)鍵點(diǎn)：
- 優(yōu)點(diǎn)：每次折半某弦，速度較快
- 缺點(diǎn)：待查表必須為順序表-->二分搜索的限制
- 復(fù)雜度：O ( log N )
什么意思桐汤？
簡而言之就是，待查表必須是有序的靶壮，無序的話必須先排序怔毛，比如在數(shù)組二分搜索某個(gè)數(shù)的時(shí)候
舉個(gè)栗子：
int a[10] = {1,2,3,4,5,6,7,8,9};
int search(int K)
{
for (int i = 0; i < N; i++)
if (num[i] == K)
{
return i;
}
return -1;
}
int search(int K, int L, int R)
{
int l = L;
int r = R;
while (l <= r)
{
if(l == r && num[l] != K)
return -1;
int mid = (l + r) / 2;
if (num[mid] < K)
return search(K, mid + 1, R);
else if (num[mid] > K)
return search(K, L, mid - 1);
else
return mid;
}
return -1;
}
二分不難寫吧？
- 其實(shí)二分的思想還是蠻容易理解的
- 重點(diǎn)在于：它除了能在數(shù)組里查數(shù)用腾降，還能干啥呢拣度？
二分答案！
- 特點(diǎn)：速度快螃壤、神奇
注意：
- 答案滿足單調(diào)性
- 預(yù)估答案區(qū)間 minAns ~ maxAns
步驟：
找區(qū)間-->取中間判斷是不是答案-->折半直到找到答案
關(guān)于此類題目的一般關(guān)鍵詞：
- 最大值盡量小
- 最小值盡量大
- (在某種情況下)最小值是多少
- (在某種情況下)最大值是多少
說到這里抗果，新手可能有點(diǎn)蒙，沒關(guān)系奸晴，我們來看幾個(gè)例題：
It is the time to 舉栗子冤馏！
例題Z：買糖
小朋有個(gè)弟弟，小凱寄啼。小凱喜歡哭鼻子逮光，經(jīng)常因?yàn)闆]糖吃而哭鼻子。小朋要哄著小凱辕录，給小凱買糖吃睦霎，小朋有 N 元錢，商店老板小康賣的糖 K 元一個(gè)走诞，共有 M 個(gè)副女，小凱多吃一塊糖就少哭一次，但事實(shí)也不是任由小凱的蚣旱，他吃糖就會(huì)把糖紙亂扔碑幅，弄得校園很臟，校園里臟的程度y與小凱吃糖個(gè)數(shù)x關(guān)系是：y=x^2-20181314*x,當(dāng)校園里臟的程度超過 S 時(shí)塞绿，小凱的姐姐小林就會(huì)打她沟涨，小凱雖想吃糖但他不想挨打啊，問小凱在不被挨打的情況下异吻，最多可以少哭多少次裹赴？
數(shù)據(jù)范圍 1<=K,N,M,S<=10^9
- （這題不要當(dāng)真，瞎搞用的诀浪，測試一波O(N)與O(logN)的差距）
#include <iostream>
#include <cmath>
using namespace std;
long long n,m,k,s;
int ok=1;
bool isok(int z)
{
if(z<=m&&z*k<=n&&2*z<=s)
{
return 1;
}
else return 0;
}
int main()
{
cin>>n>>m>>k>>s;
///樸素查找
for(int i=1;i<=m;i++)
if(!isok(i))
{
cout<<"ans is "<<i<<endl;
ok=0;
break;
}
if(ok)
cout<<"ans is "<<m<<endl;
///二分查找
long long l=1,r=m;
long long ans;
while(l<=r)
{
long long mid=(l+r)/2;
if(isok(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<"ans is "<<ans;
return 0;
}
例題A：安排牛棚 ->鏈接
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int x[100005];
int c, n;
int R, L = 1e9 + 9;
int s;
int ans;
bool ansok(int key)
{
int now = 1; //now表示上一個(gè)放牛的牛棚編號棋返，因?yàn)榈谝淮卧谝惶柵Ｅ锓畔拢詎ow=1
int sum = 1; //sum表示放的牛的個(gè)數(shù)雷猪，初始時(shí)我們肯定把第一個(gè)牛棚放上牛睛竣，所以sum=1
for (int i = 2; i <= n; i++)
{
if (x[i] - x[now] >= key)
{
sum++;
now = i;
}
}
if (sum >= c)
return 1;
else
return 0;
}
int main()
{
cin >> n >> c;
for (int i = 1; i <= n; i++)
{
scanf("%d", &x[i]);
s = max(s, x[i]);
L = min(L, x[i]);
}
sort(x + 1, x + 1 + n);
R = s / c + 1;
while (L <= R)
{
int mid = (L + R) / 2;
if (ansok(mid))
{
L = mid + 1;
ans = mid;
}
else
R = mid - 1;
}
cout << ans;
return 0;
}
/*
ansok(int key) ：
我們假設(shè)key就是最小值，那么我們就嘗試按照這樣的最小值能不能把牛給安排下
如果兩個(gè)牛棚之間的距離小于key求摇，那么這個(gè)牛棚不能放牛射沟，因?yàn)槲覀円呀?jīng)假設(shè)了key是最小值
這個(gè)選擇的過程不理解的話模擬一下就可以
*/
例題B：跳石頭 ->鏈接
#include <iostream>
#include <algorithm>
using namespace std;
int N, M, L;
int minAns = 1e9 + 9;
int maxAns;
int ans;
int dis[50006];
bool ansok(int key)
{
int sum = 0;
int now = 0;
for (int i = 1; i <= N + 1; i++)
{
if (dis[i] - dis[now] < key)
sum++;
else
now = i;
}
if (sum <= M)
return 1;
else
return 0;
}
int main()
{
cin >> L >> N >> M;
for (int i = 1; i <= N; i++)
{
cin >> dis[i];
}
dis[N + 1] = L; //虛擬一個(gè)終點(diǎn) N+1
int left = 0;
int right = L;
while (left <= right)
{
int mid = (left + right) / 2;
if (ansok(mid))
{
ans = mid;
left = mid + 1;
}
else
{
right = mid - 1;
}
}
cout << ans;
return 0;
}
/*
這題有一個(gè)坑在于起點(diǎn)到終點(diǎn)的距離要大于第 N 個(gè)點(diǎn)到起點(diǎn)的距離
我們虛擬一個(gè) N+1 點(diǎn)殊者，來判斷第 N 個(gè)石頭是不是要拿走
*/
例題C：組裝玩具 ->鏈接
- 這題可以用二分解決，但不像是之前兩個(gè)題那么“模板化” 验夯，需要注意的地方要單獨(dú)處理猖吴，本題深入溝通可以私聊我QQ
#include <iostream>
#include <algorithm>
using namespace std;
struct toy
{
int a;
int b;
int c;
} s[1000006];
int n, m;
int cnt;
int ans = 0;
int sum;
int k[1000006];
bool cmp(toy x, toy y)
{
return x.c < y.c;
}
int ifok(int k) //判斷二分出的答案是否可行
{
int mm = 0;
for (int i = 0; i < n; i++)
{
if (s[i].c >= k)
return m - mm;
mm += k * s[i].b - s[i].a;
if (m - mm < 0)
return m - mm;
}
return m - mm;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> s[i].a;
for (int i = 0; i < n; i++)
{
cin >> s[i].b;
s[i].c = s[i].a / s[i].b;
sum += s[i].b;
}
sort(s, s + n, cmp);
for (int i = 0; i < n; i++)
{
if (k[cnt] != s[i].c)
k[++cnt] = s[i].c;
}
int mm = ifok(k[cnt] + 1);
if (mm == 0)
cout << cnt + 1;
else if (mm > 0)
cout << mm / sum + k[cnt] + 1;
else //本題核心：二分答案
{
int l = 0;
int r = k[cnt];
while (l <= r)
{
int mid = (l + r) / 2;
if (ifok(mid) >= 0)
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout << ans;
}
return 0;
}
cout << "Hello, QLU_ACM_club !!!" << endl;
