为什么二分出来的结果不对，一直是右端点
// 考察dfs跟二分#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int n,m,p;
int dx[]={-1,0,1,0},dy[]={0,1,0-1};
bool vis;
bool dfs(int x,int y,int P)
{
if(x==n)return true;
vis=true;
for(int i=0;i<4;i++)
{
int a=x+dx,b=y+dy;
if(a>=1&&a<=n&&b>=1&&b<=m&&!vis&&p<=P)
{
if(dfs(a,b,P))return true;
}
//p大，易true
}
return false;
}
int find()
{
int l=-1,r=1001;
while(l+1<r)
{
int mid=l+r>>1;
memset(vis,0,sizeof(vis));// 每次二分都要清空
if(dfs(1,1,mid)) r=mid;
else l=mid;
}
return r;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>p;
}
}
cout<<find()<<endl;
}
你的问题出在二分查找的逻辑上。在二分查找中，我们需要确定左端点和右端点，并计算出中间位置的值。然后根据中间位置的值来更新左端点或右端点，在下一次循环中继续进行二分查找。
在你的代码中，你只是简单地将左端点设为1，右端点设为n，但你没有更新这两个端点的值。因此，无论如何循环，都只能得到右端点的值。
正确的二分查找应该如下所示：
int left = 1; // 左端点的初始值
int right = n; // 右端点的初始值
while (left <= right) {
int middle = (left + right) / 2; // 计算中间位置的值
// 根据中间位置的值进行判断，并更新左端点或右端点的值
if (middle > m) {
// 更新右端点
right = middle - 1;
} else if (middle < m) {
// 更新左端点
left = middle + 1;
} else {
// 中间位置的值等于要查找的值
// 进行相应的操作，然后退出循环
break;
}
}
cout << middle << endl; // 输出结果
希望我的回答能够帮到你。如果还有其他问题，请随时提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]