伪代码如下：视频链接：戳
结论：
如何设置蓝红边界：
一般流程：
二分查找题啦
#include<stdio.h>
long long n,m;
long long a[1000005]={
0};
long long b[1000005]={
0};
int main()
{
scanf("%lld %lld",&n,&m);
int i;
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
}
for(i=0;i<m;i++){
scanf("%lld",&b[i]);
}
for(i=0;i<m;i++){
long long l=-1;
long long r=n;
while(l+1<r){
long long mid=l+(r-l)/2;
if(a[mid]>=b[i]){
r=mid;
}else{
l=mid;
}
}
if(b[i]==a[r])
printf("%lld ",r+1); //下标从1开始，而我录入时是从0开始
else printf("-1 ");
}
return 0;
}
来点二分答案的题
#include<stdio.h>
int ans_(long long int m,long long int a[],long long int n);
int main()
{
//参数输入
long long int n,k;
scanf("%lld %lld",&n,&k);
long long int a[100005]={
0};
long long int i;
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
}
//左右指针l、r移动
long long int l=0;
long long int r=100000001;
while(l+1<r){
long long int m=(l+r)/2;
if(ans_(m,a,n)>=k){
//小段数量sum比要求的k多，说明每条小段太短了，（推断出m长度以左的长度都太短），那么左指针右移，即l=m
l=m;
}else{
r=m;
}
}
//输出
if(l<1)printf("0");
else printf("%lld",l);
return 0;
}
//判断是否符合条件
int ans_(long long int m,long long int a[],long long int n)
{
long long int sum=0; //存当前长度m下，能切成的小段数量
long long int i;
for(i=0;i<n;i++){
sum+=a[i]/m;
}
return sum;
}
- 一开始写的是：
while(l+1!=r){
int m=(l+r)/2;
if(ans_(m,a,n)>k){
//这里是>号
l=m;
}else{
r=m;
}
}
if(r<1)printf("0"); //返回的是r
else printf("%d",r);
- 但发现结果是错的，所以改成 >=k，返回 L
- 哦，AC了，那就这样改喽，不管他啦，嘿嘿嘿
- 还有还有：
long longyyds
再看一题：砍树
呃呃呃，，，异曲同工。。。。
好题：跳石头
好题解：ShawnZhou、Michael_Li
#include<stdio.h>
int fun(int mid);
int d,n,m; //d是起点和终点的距离，n是石头总数，m是要搬走的石头数
int a[50005]={
0};
int main()
{
scanf("%d %d %d",&d,&n,&m);
int i;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
a[0]=0; // 岸边就是出发点
a[n+1]=d; // 第n+1块石头就是终点，也是岸边
int l=-1;
int r=d+1;
while(l+1<r){
int mid=l+(r-l)/2; //假设的最短跳跃距离的最大值
if(fun(mid)>m){
// 如果假设的mid距离代入函数出来的 要搬走的石头数cnt 大于题目要求的m
r=mid; // 则说明假设的 最短跳跃距离的最大值mid 偏大，整体距离应该再小一些，因此把距离的上界往下拉
}else{
l=mid;
}
}
printf("%d",l);
return 0;
}
int fun(int mid)
{
int cnt=0,i=0,now=0; // cnt是要搬走的石头数，i是准备要跳的石头，now是他站的地方（石头）
for(i=1;i<=n+1;i++){
//是n+1，比较岸边和最后一块石头的距离
if(a[i]-a[now]>=mid){
now=i; //不然我就跳过来
}else{
cnt++; //如果距离小于我二分的答案mid，那么这块石头需要搬走
}
}
return cnt;
}
- 一开始写的是：
int l=0; // 得按模板来l=-1 //木材加工里因为有限制最小为1,所以写l=0
int r=d; //得按模板来r=d+1
while(l+1<r){
int mid=l+(r-l)/2;
if(fun(mid)>=m){
// 这里是>=
r=mid;
}else{
l=mid;
}
}
printf("%d",r); // 这里是r
- 然后，改改就ok啦啦啦，这题数据没有很大，所以不用开long long