20241109课程记录|陈鸿宇|二分

admin

家长你好，陈鸿宇同学20241109学习内容如下：
【课堂内容】
1.学习二分算法；
3.解析查找数字问题，分析边界变化；
4.解析砍树、银行贷款等二分查找问题；
5.分析跳石头等二分答案问题。
【学情分析】
本次课程主讲二分算法，二分算法与搜索算法均具备规则有序，算法固定的特征，需在理解的基础上辅助练习加深印象，课程中对二分算法的基础构架进行了解析，借助例题分析了二分查找与二分答案的算法构建过程。小陈同学课上表现良好，基本理解了二分算法的基本使用方法。
【课后作业】
完成作业网中T2036跳石头问题。

ice_pick

Help!

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
int cmp(int x,int y)
{
	return x<y;
 } 
int l,n,m,a[50001],li,r,b[50001],mid,cnt=0;
int main()
{
	scanf("%d %d %d",&l,&n,&m);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i+1]=abs(a[i+1]-a[i]);
	}
	b[1]=a[1];
	b[n]=l-a[n];
	sort(b,b+n,cmp);
	r=l;
	li=b[1];
	
	for(int i=1;i<=n;i++)
	{
		mid=(li+r)/2;
		if(mid>b[i])
		{
			cnt++;	
		} 
		if(cnt>m)
		{
			r=mid-1;
		}
		else
		{
			if(cnt<m)
			{
				li=mid-1;
			}
		}
	}
	cout<<li;
 } 

admin