STO#y总#Or2

二分:check函数+两模板;(前提是已经排好序才能二分)

假设有一个总区间,经由我们的 check 函数判断后,可分成两部分,
这边以o作 true,…..作 false 示意较好识别

如果我们的目标是下面这个v,那么就必须使用模板 1(r=mid)

…………….vooooooooo

假设经由 check 划分后,整个区间的属性与目标v如下,则我们必须使用模板 2(l=mid)

oooooooov……………….

所以下次可以观察 check 属性再与模板1 or 2 互相搭配就不会写错啦

 

1.【深基13.例1】查找

 题目链接:https://www.luogu.com.cn/problem/P2249

秒杀题,没啥解释的,直接上代码:

 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 const int N=1e6+10;
 5 int q[N];
 6 int main()
 7 {
 8     scanf("%d%d",&n,&m);
 9     for(int i=1;i<=n;i++)scanf("%d",&q[i]);
10     while(m--)
11     {
12         int x;
13         scanf("%d",&x);
14         int l=1,r=n;
15         while(l<r)
16         {
17             int mid=l+r>>1;
18             if(q[mid]>=x)r=mid;
19             else l=mid+1;
20         }
21         if(q[l]!=x)printf("%d ",-1);
22         else printf("%d ",l);
23     }
24 }

 2.进击的奶牛

题目链接:P1824 进击的奶牛 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 int q[N];
 5 int n,m;
 6 bool check(int x)
 7 {
 8     int cnt=1,tmp=q[1];
 9     for(int i=2;i<=n;i++)
10     {
11         if(q[i]-tmp>=x)
12         {
13             cnt++;
14             tmp=q[i];
15         }
16     }
17     return cnt>=m;
18 }
19 int main()
20 {
21     cin>>n>>m;
22     for(int i=1;i<=n;i++)cin>>q[i];
23     sort(q+1,q+1+n);
24     int l=0,r=1e9;
25     while(l<r)
26     {
27         int mid=l+r+1>>1;
28         if(check(mid))l=mid;
29         else r=mid-1;
30     }
31     cout<<l;
32 }

3.跳石头

原题链接:P2678 [NOIP2015 提高组] 跳石头 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路
一眼看到题目中的这一句话:使得选手们在比赛过程中的最短跳跃距离尽可能长,当出现最小值最大或最大值最小或求最大值、最小值时,就可以考虑一下二分了

很显然,这道题我们求的是最短距离,所以我们二分的就是最短距离。

首先验证答案具有单调性:拿走的石头越多,最短跳跃距离越大,这就叫答案的单调性。

然后进行实现。我们假设最短跳跃距离为mid,接着我们写一个check函数,判断一下这个mid是否合法,如果合法,就尝试找一找有没有一个值比mid更大(l=mid),如果不合法,就把mid减小(r=mid-1)。

check函数:我们遍历一遍每一块石头,累计出有多少块石头之间的间隔<=mid,如果超过m个,就不合法,如果小于等于m,就合法。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int s,n,m;
 4 const int N=1e6+10;
 5 int q[N];
 6 bool check(int x)
 7 {
 8     int cnt=0;int last=0;
 9     for(int i=1;i<=n;i++)
10     {
11         if(q[i]-last<x)cnt++;//
12         else last=q[i];
13     }
14     return cnt<=m;
15 }
16 int main()
17 {
18     scanf("%d%d%d",&s,&n,&m);
19     for(int i=1;i<=n;i++)scanf("%d",&q[i]);
20     int l=1,r=1e9+10;
21     q[n+1]=s;
22     n+=1;
23     while(l<r)
24     {
25         int mid=l+r+1>>1;
26         if(check(mid))l=mid;
27         else r=mid-1;
28     }
29     cout<<l;
30 }

4.P1024 [NOIP2001 提高组] 一元三次方程求解

 原题链接:P1024 [NOIP2001 提高组] 一元三次方程求解 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

观察100/0.01=1e4 爆搜!!!这题我是真不知道咋二分(复杂捏)qwq

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 double a,b,c,d;
 4 int main()
 5 {
 6     scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
 7     for(double i=-100;i<100;i+=0.01)
 8       if(fabs(i*i*i*a+i*i*b+i*c+d)<1e-4)//必须加绝对值,因为当趋近于0时候在x轴上下均符合
 9         printf("%.2lf ",i);
10 }

5.P1873 [COCI 2011/2012 #5] EKO / 砍树

原题链接:P1873 [COCI 2011/2012 #5] EKO / 砍树 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题一定要LL啊(哭),开1e6就够了,开1e9当时直接炸了…

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 LL q[1000005];
 5 LL m,n;
 6 typedef long long LL;
 7 bool check(LL x)
 8 {
 9     LL sum=0;
10     for(LL i=0;i<n;i++)
11     {
12         if(q[i]>x)sum+=q[i]-x;
13     }
14     return sum>=m;
15 }
16 int main()
17 {
18     cin>>n>>m;
19     for(LL i=0;i<n;i++)cin>>q[i];
20     LL l=1,r=1e9;
21     while(l<r)
22     {
23         LL mid=l+r+1>>1;
24         if(check(mid))l=mid;
25         else r=mid-1;
26     }
27     cout<<l;
28 }

6.三分法(反正不会三分,,看还有人用粒子群优化(Particle Swarm Optimization,PSO)做的)

我只会求导qwq 

原题链接:P3382 【模板】三分法 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

浮点数二分不用照顾边界!!!安心二分就行了!!!不用加一减一的麻烦自己!!!

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 double l,r;
 5 double a[15];//存系数
 6 bool check(double x)
 7 {
 8     double lim=0;
 9     for(int i=0;i<n;i++)
10     {
11         lim+=a[i]*pow(x,i);
12     }
13     return lim>0;
14 }
15 int main()
16 {
17     cin>>n>>l>>r;
18     for(int i=n;i>=0;i--)
19     {
20         double x;
21         cin>>x;
22         if(i==0)break;
23         a[i-1]=x*i;
24     }
25     while(r-l>1e-7)
26     {
27         double mid=(l+r)/2;//浮点数二分不需要+1,本来就是准确的,虽然写的时候加了然后就卡了好久....
28         if(check(mid))l=mid;
29         else r=mid;//浮点二分直接取中点,不用减一 要是-1就会有可能造成死循环
30     }
31     cout<<fixed<<setprecision(5)<<l;
32 }

二分算是浅浅掌握了,呼~呲饭

 

原文地址:http://www.cnblogs.com/Zac-saodiseng/p/16852031.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性