二分例题（D.负重越野，I.路径规划）

本文主要是介绍二分例题（D.负重越野，I.路径规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这两天的训练赛都有一道二分的题，但是都没往二分上面想，同样不知道怎么二分。

D. Fast and Fat

思路

二分的关键也就是check函数怎么写了，求队伍最大速度，可以分为速度>=mid和<mid两部分，再判断，能不能实现速度大的背小的，并且速度>=mid.

代码

#include<bits/stdc++.h>
using namespace std;
# define int long long
int n;
struct pi{int v,w;
}a[100005];
bool cmp1(pi a,pi b)
{return a.v+a.w>b.v+b.w;
}
bool cmp2(pi a,pi b)
{return a.w>b.w;
}
int check(int x)
{vector<pi> s;//存放速度小的，需要被背着vector<pi> q;//存速度大的，for(int i=1;i<=n;i++){if(a[i].v>=x)q.push_back(a[i]);else s.push_back(a[i]);}if(q.size()<s.size())return 0;sort(q.begin(),q.end(),cmp1);//速度可能会变为vi+wi-wj,所以按vi+wi的大小顺序排sort(s.begin(),s.end(),cmp2);//w从大到小排。//无需考虑太多，如果最大的vi+wi去背wj,速度达不到，那也不用考虑其他的了，必须要保证每个小的都被背for(int i=0;i<s.size();i++){if(q[i].v+q[i].w-s[i].w<x)return 0;}return 1;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i].v>>a[i].w;int l=-1,r=1e9+10;while(l<r)//这是小于等于最大值的二分{int mid=(l+r+1)>>1;if(check(mid))l=mid;else   r=mid-1;	}cout<<l<<'\n';
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie();int t;cin>>t;while(t--){solve();}
}

I. Path Planning

思路

用一个map,键存位置，值存数字，关于check函数，我一直想的都是i,j，i+j…但这些其实可以不考虑，要满足向右下走，用两重循环，i的值在不断增大，此时已经是向下，这时只需要，设个变量判断j,就可以了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<pair<int,int>,int> ma;
int n,m;
int check(int x)//这样判断很巧妙，而且首尾数字是什么，都无关紧要
{int k=0;for(int i=1;i<= n;i++)for(int j=1;j<= m;j++)//如果是一行或一列，不需要特殊考虑，因为j逐步增大{if(ma[{i,j}]<x){if(j<k) return 0;k=j;}}return 1;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>ma[{i,j}];//这里将map和pair结合，赛时也没想到int l=0,r=n*m;while(l<r){int mid=l+r+1>>1;if(check(mid))l=mid;else 	r=mid-1;	}cout<<l<<'\n';
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}
}