二分查找普通模式
模板公式：
while(l<=r){
mid=(l+r)/2;
l=mid+1;
else r=mid-1;
}
二分查找特殊情况1：
000011111求第一个1.
while(l!=r){
mid=(l+r)/2;
l=mid+1;
r=mid;
}
对于给定的一个长度为 N 的正整数数列 Ai，现要将其分成 M(M≤N) 段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 4 2 4 5 1 要分成 3 段
将其如下分段：
[4 2][4 5][1]
第 1 段和为 6，第 2 段和为 9，第 3 段和为 1，和最大值为 9。
将其如下分段：
[4][2 4][5 1]
第 1 段和为 4，第 2 段和为 6，第 3 段和为 6，和最大值为 6。
并且无论如何分段，最大值不会小于 6。
所以可以得到，要将数列 4 2 4 5 1 分成 3 段，每段和的最大值最小为 6。
#include<bits/stdc++.h>
using namespace std;
long long n,m,num[100005],l,r;
long long func(long long x){
long long t=0,now=0;
for(int i=0;i<n;i++)
{
if(now+num[i]>x){
t++;
now=num[i];
}else if(now+num[i]==x)
{
t++;
now=0;
}else{
now+=num[i];
}
}
if(now!=0)
{
t++;
}
return t;
}
long long bs(){
while(l!=r)
{
long long mid=(l+r)/2;
long long s=func(mid);
if(s<=m){
r=mid;
}else {
l=mid+1;
}
}
return l;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>num[i];
l = max(l,num[i]);
r += num[i];
}
cout<<bs()<<endl;
return 0;
}
特殊情况二
111110000求最后一个1.
while(l!=r){
mid=(l+r+1)/2;
l=mid;
r=mid-1;
}
某林业局现在 N根原木，长度分别为 Xi，为了便于运输，需要将他们切割成长度相等的 M根小段原木（只能切割成整数长度，可以有剩余），小段原木的长度越大越好，现求小段原木的最大长度。例如，有 3根原木长度分别为 6,15,22，现在需要切成 8 段，那么最大长度为 5。
#include<iostream>
using namespace std;
int n,m,num[1000005],tr;
int func(int x) {
int t=0;
for (int i=0;i<n;i++){
t+=num[i]/x;
}
return t;
}
int bs(){
int l=1,r=tr;
while(l!=r){
int mid=(l+r+1)/2;
int s = func(mid);
if (s >= m) {
l = mid;
}else {
r = mid-1;
}
}
return l;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>num[i];
tr=max(tr,num[i]);
}
cout<<bs()<<endl;
return 0;
}
特殊情况三
数组为小数时
while(r-l>0.00001){
mid=(l+r)/2;
l=mid;
r=mid;
}
有 N 条绳子，它们的长度分别为 Li。如果从它们中切割出 KK条长度相同的绳子，这 K条绳子每条最长能有多长？答案保留到小数点后 2 位(直接舍掉 2 位后的小数)。
#include<bits/stdc++.h>
using namespace std;
int n, m;
double num[10005],tr;
int func(double x){
int t=0;
for(int i=0;i<n;i++)
{
t+=num[i]/x;
}
return t;
}
double bs(){
double l=0,r=tr;
while(r-l>0.00001)
{
double mid = (l+r)/2;
double s=func(mid);
if(s>=m){
l=mid;
}else {
r=mid;
}
}
return l;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>num[i];
tr = max(tr,num[i]);
}
double t=bs();
printf("%.2f\n",t-0.005);
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
