二分枚舉

適用條件：

• 答案有明顯上下界
• 答案具有單調性:a滿足,若b>=a可以知b必定滿足。
• 本質上是枚舉的對數優化

思維技巧

• 解決問題->>驗證答案,明顯前者比后者更加困難
• 若題目有最大值最小，最小值最大這種經典條件，隱含著答案有界

模板

• 左邊界和右邊界的界定
• 判定函數
• 二分模板

bool isValid(){//驗證答案
}
int l==a,r=b;
while(l<=r){int mid=(l+r)/2if(isValid(mid)){ans=mid;l=mid+1;}else{r=mid-1;}
}

---

以下均為題解

小鳥的設備

題目背景

小鳥有 $n$ 個可同時使用的設備。

題目描述

第 $i$ 個設備每秒消耗 $a_i$ 個單位能量。能量的使用是連續的，也就是說能量不是某時刻突然消耗的，而是勻速消耗。也就是說，對于任意實數，在 $k$ 秒內消耗的能量均為 $k\times a_i$ 單位。在開始的時候第 $i$ 個設備里存儲著 $b_i$ 個單位能量。

同時小鳥又有一個可以給任意一個設備充電的充電寶，每秒可以給接通的設備充能 $p$ 個單位，充能也是連續的，不再贅述。你可以在任意時間給任意一個設備充能，從一個設備切換到另一個設備的時間忽略不計。

小鳥想把這些設備一起使用，直到其中有設備能量降為 $0$。所以小鳥想知道，在充電器的作用下，她最多能將這些設備一起使用多久。

輸入格式

第一行給出兩個整數 $n,p$。

接下來 $n$ 行，每行表示一個設備，給出兩個整數，分別是這個設備的 $a_i$ 和 $b_i$。

輸出格式

如果小鳥可以無限使用這些設備，輸出 $?1$。

否則輸出小鳥在其中一個設備能量降為 $0$ 之前最多能使用多久。

設你的答案為 $a$，標準答案為 $b$，只有當 $a,b$ 滿足
$\frac{|a?b|}{\max (1,b)}\le 10^{?4}$ 的時候，你能得到本測試點的滿分。

解題思路

• 注意題目描述：能量的使用是連續的，意味著可以從整體來看問題，如果充電量大于總耗電量，則一定可以無限使用，反之則不能。
• 直接表達問題非常困難，但是從枚舉的角度驗證答案其實不難
• 注意精度

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
double p,ans=0;
vector<double>e(100009, 0); //當前電力
vector<double>ct(100009, 0);//消耗bool isValid(double s,vector<double>e) {for (int i = 1; i <= n; i++) {e[i] -= ct[i] * s;}double sum = p * s;for (int i = 1; i <= n; i++) {if (e[i] < 0) {sum += e[i];}if (sum < 0) {return false;}}return true;
}
void solve() {cin >> n >> p;double sume = 0;//總電力double cost = 0;for (int i = 1; i <= n; i++) {cin >> ct[i] >> e[i];sume += e[i];cost += ct[i];}if (cost <= p) {cout << -1;return;}double time = sume / (cost - p);//最大時間//cout << "sume==" << sume << " cost==" << cost <<" time==" <<time<< endl;double l = 0, r = time;while (l <= r) {double mid = (l+r)/2;if (isValid(mid, e)) {ans = mid;l = mid + 1e-5;}else {r = mid - 1e-5;}}printf("%f", ans);}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}

[COCI 2011/2012 #5] EKO / 砍樹

題目描述

伐木工人 Mirko 需要砍 $M$ 米長的木材。對 Mirko 來說這是很簡單的工作，因為他有一個漂亮的新伐木機，可以如野火一般砍伐森林。不過，Mirko 只被允許砍伐一排樹。

Mirko 的伐木機工作流程如下：Mirko 設置一個高度參數 $H$（米），伐木機升起一個巨大的鋸片到高度 $H$，并鋸掉所有樹比 $H$ 高的部分（當然，樹木不高于 $H$ 米的部分保持不變）。Mirko 就得到樹木被鋸下的部分。例如，如果一排樹的高度分別為 $20,15,10$ 和 $17$，Mirko 把鋸片升到 $15$ 米的高度，切割后樹木剩下的高度將是 $15,15,10$ 和 $15$，而 Mirko 將從第 $1$ 棵樹得到 $5$ 米，從第 $4$ 棵樹得到 $2$ 米，共得到 $7$ 米木材。

Mirko 非常關注生態保護，所以他不會砍掉過多的木材。這也是他盡可能高地設定伐木機鋸片的原因。請幫助 Mirko 找到伐木機鋸片的最大的整數高度 $H$，使得他能得到的木材至少為 $M$ 米。換句話說，如果再升高 $1$ 米，他將得不到 $M$ 米木材。

輸入格式

第 $1$ 行 $2$ 個整數 $N$ 和 $M$，$N$ 表示樹木的數量，$M$ 表示需要的木材總長度。

第 $2$ 行 $N$ 個整數表示每棵樹的高度。

輸出格式

$1$ 個整數，表示鋸片的最高高度。

解題思路

• 正常的二分
• 枚舉+最大

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,ans=0;
ll m; vector<int>v(1000009, 0);
bool isValid(int mid) {ll sum = 0;for (int i = 1; i <= n;i++) {if (mid > v[i]) {continue;}sum += (ll)(v[i] - mid);}if (sum >= m)return true;return false;
}
void solve() {cin >> n >> m;int maxlen = 0;for (int i = 1; i <= n; i++) {cin >> v[i];maxlen = max(v[i], maxlen);}int l = 0, r = maxlen;while (l <= r) {int mid = (l + r) / 2;/*cout << mid << endl;*/if (isValid(mid)) {ans = mid;l=mid+1;}else {r= mid - 1;}}cout << ans;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}

數列分段 Section II

題目描述

對于給定的一個長度為 $N$ 的正整數數列 $A_{1～N}$，現要將其分成 $M$（$M\le N$）段，并要求每段連續，且每段和的最大值最小。

關于最大值最小：

例如一數列 $42451$ 要分成 $3$ 段。

將其如下分段：

$$[42][45][1]$$

第一段和為 $6$，第 $2$ 段和為 $9$，第 $3$ 段和為 $1$，和最大值為 $9$。

將其如下分段：

$$[4][24][51]$$

第一段和為 $4$，第 $2$ 段和為 $6$，第 $3$ 段和為 $6$，和最大值為 $6$。

并且無論如何分段，最大值不會小于 $6$。

所以可以得到要將數列 $42451$ 要分成 $3$ 段，每段和的最大值最小為 $6$。

輸入格式

第 $1$ 行包含兩個正整數 $N,M$。

第 $2$ 行包含 $N$ 個空格隔開的非負整數 $A_i$，含義如題目所述。

輸出格式

一個正整數，即每段和最大值最小為多少。

解題思路

• 判定函數：我感覺我的判定函數沒起到作用，因為當區間長度為1時，如果和sum>枚舉值時，這個枚舉值一定是無效的。
  但是如果不加入l=maxv對二分左邊界作限制，又過不了…
• 應該對二分邊界作詳細界定，不能忽略的左邊界！！！

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m,ans=0;
vector<int>v(100009, 0);
bool isValid(ll t,int m) {//t目標值，m是段數ll sum = 0;int i = 1;for (int j = 1; j <= n; j++) {sum += (ll)v[j];if (sum > t) {if (i < j) {sum = (ll)v[j];i = j;m--;}else {return false;}}}if (m < 1) {return false;}return true;
}
void solve() {cin >> n >> m;ll maxv = 0,sum=0;for (int i = 1; i <= n; i++) {cin >> v[i];maxv = max(maxv, (ll)v[i]);sum += (ll)v[i];}/*cout << "maxv==" << maxv <<" sum=="<<sum<< endl;*/ll l = maxv, r = sum,mid=0;while (l <= r) {mid = (l + r) / 2;if (isValid(mid, m)) {ans = mid;r = mid - 1;}else {l = mid + 1;}}cout << ans;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}

煩惱的高考志愿

題目背景

計算機競賽小組的神牛 V 神終于結束了高考，然而作為班長的他還不能閑下來，班主任老 t 給了他一個艱巨的任務：幫同學找出最合理的大學填報方案。可是 v 神太忙了，身后還有一群小姑娘等著和他約會，于是他想到了同為計算機競賽小組的你，請你幫他完成這個艱巨的任務。

題目描述

現有 $m$ 所學校，每所學校預計分數線是 $a_i$。有 $n$ 位學生，估分分別為 $b_i$。

根據 $n$ 位學生的估分情況，分別給每位學生推薦一所學校，要求學校的預計分數線和學生的估分相差最小（可高可低，畢竟是估分嘛），這個最小值為不滿意度。求所有學生不滿意度和的最小值。

輸入格式

第一行讀入兩個整數 $m,n$。$m$ 表示學校數，$n$ 表示學生數。

第二行共有 $m$ 個數，表示 $m$ 個學校的預計錄取分數。第三行有 $n$ 個數，表示 $n$ 個學生的估分成績。

輸出格式

輸出一行，為最小的不滿度之和。

樣例 #1

樣例輸入 #1

4 3
513 598 567 689
500 600 550

樣例輸出 #1

32

思路

• 二分枚舉答案
• 優化O(n*n)至O(nlogn)
• 注意l=0，因為我排序了！！！下標從0開始了！！！！！

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int m, n;
vector<ll>student(100009, 0);
vector<ll>school(100009, INT_MAX);
ll search(int target) {ll l = 0, r = m,mid=0;ll minval = INT_MAX;while (l <= r) {mid = (l + r) / 2;      if (school[mid] < target) {minval = min(minval, abs(school[mid] - target));l = mid + 1;}else if (school[mid] == target) {return 0;}else {minval = min(minval, abs(school[mid] - target));r = mid - 1;}}return minval;
}
void solve() {cin >> m >> n;for (int i = 1; i <= m; i++) {cin >> school[i];}for (int i = 1; i <= n; i++) {cin >> student[i];}sort(school.begin(), school.end());//排序后下標改變了！！！ll sum = 0;for (int i = 1; i <= n; i++) {sum += search(student[i]);}cout << sum;
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);solve();return 0;
}