当前位置：首页 > news >正文

C++：二分习题

news 来源：原创 2025/8/19 2:02:35

1. 借教室

503. 借教室 - AcWing题库

在大学期间，经常需要租借教室。

大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。

教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 nn 天的借教室信息，其中第 ii 天学校有 riri 个教室可供租借。

共有 mm 份订单，每份订单用三个正整数描述，分别为 dj,sj,tjdj,sj,tj，表示某租借者需要从第 sjsj 天到第 tjtj 天租借教室（包括第 sjsj 天和第 tjtj 天），每天需要租借 djdj 个教室。

我们假定，租借者对教室的大小、地点没有要求。

即对于每份订单，我们只需要每天提供 djdj 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。

如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。

这里的无法满足指从第 sjsj 天到第 tjtj 天中有至少一天剩余的教室数量不足 djdj 个。

现在我们需要知道，是否会有订单无法完全满足。

如果有，需要通知哪一个申请人修改订单。

解题思路

这个题我们可以用二分来枚举mod个订单是否可以完成任务，如果全部完成了输出0，反之输出不行的订单号。寻找的是不行的最小的

判断是否可以完成订单可以用差分数组，来记录每个区间的改变，然后将差分数组加起来与可租借的教室数量进行比较，如果订单使用的教室数量大于可租借的教室数量就是失败了

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=1000010;
int n, m;
int r[N];
int d[N];//数量
int s[N];//开始
int t[N];//结束
long long b[N+1];//差分数组
bool check(int mid)
{memset(b, 0, sizeof(b));for (int i = 1; i <= mid; i++){b[s[i]] += d[i];b[t[i] + 1] -= d[i];}for (int i = 1; i <= n; i++){b[i] += b[i - 1];if (b[i] > r[i])return false;}return true;}
int main()
{scanf("%d%d", &n, &m);//天数和订单数量for (int i = 1; i <= n; i++){scanf("%d", &r[i]);//表示第i天可以租接的教室数量}for (int i = 1; i <= m; i++){scanf("%d%d%d", &d[i], &s[i], &t[i]);//数量，开始，结束分别在第几天}int l = 0, r = m;//l=0;防止极端情况//订单增多,区间单调递减while (l  < r){int mid = (l + r+1) / 2;//防止最后取不到r本身if (check(mid)) l = mid;elser = mid -1;//证明mid是不可以的所以取前面一个}if (r == m)//满足了printf("0");elseprintf("-1\n%d\n", r + 1);//因为r会取到不可以的前一个数所以加1return 0;
}

2.分巧克力

1227. 分巧克力 - AcWing题库

儿童节那天有 KK 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 NN 块巧克力，其中第 ii 块是 Hi×WiHi×Wi 的方格组成的长方形。

为了公平起见，小明需要从这 NN 块巧克力中切出 KK 块巧克力分给小朋友们。

切出的巧克力需要满足：

形状是正方形，边长是整数
大小相同

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 22 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

解题思路

由于是正方形的所以可以直接二分枚举一个边长，判断这个边长是否可以分割成k块巧克力,寻找可以到k块的最大边长。

我们计算出这个能分割出几块巧克力即可

AC代码

#include<iostream>
#include<cstdio>int k,n;int h[100005];
int w[100005];int max=0;//巧克力最短的长或高bool chock(int wh)
{int s=0;//切开相同大小巧克力的数量// for(int i=0;i<n;i++)// { //     int w1=w[i];//     int h1=h[i];//     while(w1>=wh)//     {//         s+=h1/wh;//         w1-=wh;//     }// }for(int i=0;i<n;i++){int w1=w[i]/wh;int h1=h[i]/wh;s+=w1*h1;}if(s>=k)return true;elsereturn false;
}int main()
{scanf("%d%d",&n,&k);//n个巧克力，k个人for(int i=0;i<n;i++){scanf("%d%d",&h[i],&w[i]);if(h[i]>max)max=h[i];if(w[i]>max)max=w[i];}int l=0;int r=max;while(l<r){int mid=l+(r-l+1)/2;if(chock(mid)){l=mid;}elser=mid-1;}printf("%d",l);return 0;
}

3.冶炼金属

4956. 冶炼金属 - AcWing题库

小蓝有一个神奇的炉子用于将普通金属 OO 冶炼成为一种特殊金属 XX。

这个炉子有一个称作转换率的属性 VV，VV 是一个正整数，这意味着消耗 VV 个普通金属 OO 恰好可以冶炼出一个特殊金属 XX，当普通金属 OO 的数目不足 VV 时，无法继续冶炼。

现在给出了 NN 条冶炼记录，每条记录中包含两个整数 AA 和 BB，这表示本次投入了 AA 个普通金属 OO，最终冶炼出了 BB 个特殊金属 XX。

每条记录都是独立的，这意味着上一次没消耗完的普通金属 OO 不会累加到下一次的冶炼当中。

根据这 NN 条冶炼记录，请你推测出转换率 VV 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

解题思路

我们用二分枚举转换率V，普通金属数量/mid(枚举的V)<=特殊金属时，说明这个是符合的，所以边界r变为mid，如果不能达成目标，边界l变为mid，最后的r就是符合的最小值。

最大值怎么求呢？

我们转换一下思维，我们求了B个金属的最小转换率，那就能求B-1的最小转换率，B-1的最小转换率-1就是B的最大转换率

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;int get(int a,int b)
{int l=0,r=1e9+2;while(l+1<r){int mid=(l+r)/2;if(a/mid<=b) r=mid;//将数值调到else l=mid;}return r;
}
int main()
{scanf("%d",&n);int minn=0,maxx=1e9+1;for(int i=0;i<n;i++){    int a,b;scanf("%d %d",&a,&b);minn=max(minn,get(a,b));//maxx=min(maxx,get(a,b-1)-1);//}printf("%d %d",minn,maxx);//第一个是最小值，第二个是最大值
}

4.最佳牛围栏

102. 最佳牛围栏 - AcWing题库

农夫约翰的农场由 NN 块田地组成，每块地里都有一定数量的牛，其数量不会少于 11 头，也不会超过 20002000 头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 FF 块地，其中 FF 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

解题思路

计算连续f块地或f块以上的最大平均值(每块地的牛)，利用二分答案，注意处理浮点数的时候，由于精度问题，不能用整数二分的方法直接比较相等，而是需要设置一个误差范围，我们这里写r-l<1e-5 。判断平均mid头牛是否可以

我们预处理一下前缀和，每块地都减去我们二分答案枚举的mid，即只有这块区间平均值大于mid，才会>0。我们利用双指针，记录平均值最小的区间差了多少(minv初始值为0，只有遇见负数也就是小于mid这个平均值时才会更新)，再判断我们现在枚举的到j这个区间的平均值将小于平均值最多的减去(例如 2 2 3 4 这组数，我们枚举的mid为3， aver[2]就是-2 ，然后我们到 aver[4]时，就要减去前面的值，就是不算前面的区间)看是否>=mid这个平均值大于就返回true。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;int n,f;//总共有n块地，包f块地
long long s[100010];
double aver[100010];//前缀和数组bool check(double mid)
{for(int i=1;i<=n;i++){aver[i]=aver[i-1]+s[i]-mid;//每个都减去牛的平均值即加上小于平均值的牛会让平均值变小}double minv=0;for(int i=0,j=f;j<=n;j++,i++){//即是把一段平均值小的摘出来，在if里从总值筛出去minv=min(minv,aver[i]);//如果aver[i]大就取这个区间，区间长度仍为f，否则，区间长度就是f-i+上一次的iif(aver[j]-minv>=0)//说明当前的平均mid头牛可以或者还能更多。说明我们当前枚举的区间是把前面平均值小的区间筛出去了return true;}return false;
}int main()
{scanf("%d%d",&n,&f);for(int i=1;i<=n;i++){scanf("%lld",&s[i]);}double l=1,r=2000;//二分答案while(r-l>1e-5)//浮点数二分{double mid=(r+l)/2;if(check(mid))//{l=mid;}else//这个答案不可以r=mid;}printf("%d",int(r*1000));
}

5.青蛙过河

P8775 [蓝桥杯 2022 省 A] 青蛙过河 - 洛谷

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。当小青蛙具有一个跳跃能力 y 时，它能跳不超过 y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

解题思路

先做一个前缀和，方便统计一个区间内能跳的次数。

青蛙从左跳到右和从右跳到左实际是没有区别的，和从左到右跳2x次是一样的。

这个青蛙能跳到的一个区间内石头必须是>=2*x的，我们假设一个数据，以小见大，(n=5 x=1 石头高度为 2 0 2 0 这组数据，当枚举步数是2 时，每个长度为2的区间都是满足>=2*x的所以可以)

所以双指针，枚举区间进行判断即可。

AC代码

#include<iostream>
#include<cstdio>using namespace std;int n, x;
int d[100010] = { 0 };bool check(int y)
{for (int i = y; i < n; i++){if (d[i ] - d[i-y] < 2 * x)//这个区间石头高度不到2*x就不可以{return false;}}return true;
}int main()
{scanf("%d%d", &n, &x);//n是宽度，即离对岸的距离int h;for (int i = 1; i < n; i++){scanf("%d", &h);d[i] += h + d[i - 1];//前缀和}int l = 1, r = n ;while (l < r){int mid = (l + r) / 2;// cout << "mid:  " << mid << endl;if (check(mid))//如果可以{r = mid;}elsel = mid + 1;}printf("%d", r);return 0;
}

这篇就到这里了(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤

1. 借教室

解题思路

AC代码

2.分巧克力

解题思路

AC代码

3.冶炼金属

解题思路

AC代码

4.最佳牛围栏

解题思路

5.青蛙过河

解题思路

AC代码

相关文章：