二分枚举
适用条件:
- 答案有明显上下界
- 答案具有单调性:a满足,若b>=a可以知b必定满足。
- 本质上是枚举的对数优化
思维技巧
- 解决问题->>验证答案,明显前者比后者更加困难
- 若题目有最大值最小,最小值最大这种经典条件,隐含着答案有界
模板
- 左边界和右边界的界定
- 判定函数
- 二分模板
bool isValid(){
//验证答案
}
int l==a,r=b;
while(l<=r){
int mid=(l+r)/2
if(isValid(mid)){
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
以下均为题解
小鸟的设备
题目背景
小鸟有 个可同时使用的设备。
题目描述
第 个设备每秒消耗 个单位能量。能量的使用是连续的,也就是说能量不是某时刻突然消耗的,而是匀速消耗。也就是说,对于任意实数,在 秒内消耗的能量均为 单位。在开始的时候第 个设备里存储着 个单位能量。
同时小鸟又有一个可以给任意一个设备充电的充电宝,每秒可以给接通的设备充能 个单位,充能也是连续的,不再赘述。你可以在任意时间给任意一个设备充能,从一个设备切换到另一个设备的时间忽略不计。
小鸟想把这些设备一起使用,直到其中有设备能量降为 。所以小鸟想知道,在充电器的作用下,她最多能将这些设备一起使用多久。
输入格式
第一行给出两个整数 。
接下来 行,每行表示一个设备,给出两个整数,分别是这个设备的 和 。
输出格式
如果小鸟可以无限使用这些设备,输出 。
否则输出小鸟在其中一个设备能量降为 之前最多能使用多久。
设你的答案为 ,标准答案为 ,只有当 满足
的时候,你能得到本测试点的满分。
解题思路
- 注意题目描述:能量的使用是连续的,意味着可以从整体来看问题,如果充电量大于总耗电量,则一定可以无限使用,反之则不能。
- 直接表达问题非常困难,但是从枚举的角度验证答案其实不难
- 注意精度
#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 需要砍 米长的木材。对 Mirko 来说这是很简单的工作,因为他有一个漂亮的新伐木机,可以如野火一般砍伐森林。不过,Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下:Mirko 设置一个高度参数 (米),伐木机升起一个巨大的锯片到高度 ,并锯掉所有树比 高的部分(当然,树木不高于 米的部分保持不变)。Mirko 就得到树木被锯下的部分。例如,如果一排树的高度分别为 和 ,Mirko 把锯片升到 米的高度,切割后树木剩下的高度将是 和 ,而 Mirko 将从第 棵树得到 米,从第 棵树得到 米,共得到 米木材。
Mirko 非常关注生态保护,所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 ,使得他能得到的木材至少为 米。换句话说,如果再升高 米,他将得不到 米木材。
输入格式
第 行 个整数 和 , 表示树木的数量, 表示需要的木材总长度。
第 行 个整数表示每棵树的高度。
输出格式
个整数,表示锯片的最高高度。
解题思路
- 正常的二分
- 枚举+最大
#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
题目描述
对于给定的一个长度为 的正整数数列 ,现要将其分成 ()段,并要求每段连续,且每段和的最大值最小。
关于最大值最小:
例如一数列 要分成 段。
将其如下分段:
第一段和为 ,第 段和为 ,第 段和为 ,和最大值为 。
将其如下分段:
第一段和为 ,第 段和为 ,第 段和为 ,和最大值为 。
并且无论如何分段,最大值不会小于 。
所以可以得到要将数列 要分成 段,每段和的最大值最小为 。
输入格式
第 行包含两个正整数 。
第 行包含 个空格隔开的非负整数 ,含义如题目所述。
输出格式
一个正整数,即每段和最大值最小为多少。
解题思路
- 判定函数:我感觉我的判定函数没起到作用,因为当区间长度为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;
}