事情的起因是 蓝桥杯的时候二分法调了半天还错了 于是我决定重新进行一个归纳与记忆
用记忆以及运用最好的方法
对于这种有序数组的查找 我们一般称其为二分查找
例如 大致几类问题
1.寻找大于5的第一个数的下标
2.寻找大于等于5的第一个数的下标
3.寻找大于5的最后一个数的下标…诸如此类
那么如何进行记忆呢
查找关于x的 check() 如果是对对对错型 则 mid<x或mid<=x 以此来确定分界线的位置
如果是错错错对型 则将数组逆序存储
然后我们再对l r的选取进行思考
如果是mid<4: 1 2 3 |4 4 4 4 6 8 边界即在|处 l是3 小于4的第一个数 r是4 大于等于4的第一个数
如果是mid<=4 1 2 3 4 4 4 4 4| 6 8 l是大于4的最后一个数
怎么记呢 条件<4 就是在小于4的第一个数前划一竖线
<=4 就是在最后一个<=4的数的右边划一个竖线
若有N个数 则从下标为1开始存
初始化l指针为0 r指针为N+1
[二分查找] [c++]1
2
3
4
5
6
7
8
9
10
11
| int l=0,r=N+1
while(l+1!=r)
{
int mid=(l+r)/2;
if(check(q[mid]))
{
l=mid;
}
else r=mid;
}
|
单调有序数组的二分查找就到此为止了
接下来是用的最多的 二分答案 这样的题就太多了
一般分为
1.最小值最大类型(满足条件的答案越来越大)
2.最大值最小类型
[2440] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,a[N];
bool check(int x);
int main()
{
cin>>n>>k;
int longest=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>=longest) longest=a[i];
}
int l=0,r=longest;
while(l+1<r)
{
int mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
if(l<1) cout<<0<<endl;
else
{
if(check(r)) cout<<r<<endl;
else cout<<l<<endl;
}
return 0;
}
bool check(int x)
{
int sum=0;
for(int j=1;j<=n;j++)
{
sum+=(a[j]/x);
}
if(sum>=k) return true;
else return false;
}
|
[2678] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int a[N],ans;
bool check(int x,int b[],int n,int m)
{
int now=0,tot=0;
for(int j=1;j<=n+1;j++)
{
if(a[j]-a[now]<x) tot++;//如果距离小 这颗石头可以搬走
else
{
now=j;// 如果距离大,就跳过去
}
}
if(tot>m) return false;
else return true;
}
int main()
{
int L,n,m;
cin>>L>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
a[n+1]=L;
int l=1,r=L;
while(l+1<r)
{
int mid=(l+r)>>1;
if (check(mid,a,n,m))
{
l=mid;
}
else r=mid;
}
if(check(r,a,n,m)) cout<<r<<endl;
else cout<<l<<endl;
return 0;
}
|
伐木那题 切的长度越短 越能分出k段 所以是对对对对错型
跳石头 最短跳跃很小 只要到其中最大的间隔 就行 一个石头都不用移动 如果要移动石头 就把最短距离调大 那么也是对对对对错型
插路标 空旷指数是相邻路标最大距离 如果最大距离特别小 那么需要很多的路标 可能就不够 如果最大距离很大很大 不需要插路标 也可以满足 所以是错错错对型 需要改成r=mid在先
