求助大佬!两种二分的区别

P1678 烦恼的高考志愿

lyttt @ 2023-07-30 14:00:38

第一个while(l<r)二分没过,第二个while(l<=r)过了,请问是哪出问题了,什么情况下,应该怎么选用哪种啊,还是说都可以用,每次都很难调

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int m,n;
int a[N],b[N];

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    cin>>a[i];

    for(int i=1;i<=m;i++)
    cin>>b[i];

   sort(a+1,a+1+n);

   long long res=0;

   for(int i=1;i<=m;i++)
   {
      int l=1,r=n;
      int mid;

      while(l<r)
     {
      mid=(l+r+1)/2;   
      if(a[mid]<b[i])
      l=mid;
      else
      r=mid-1;
     }
     if(b[i]<=a[1]) res+=a[1]-b[i];
     else
     res+=min(abs(a[l]-b[i]),abs(a[r]-b[i]));
   }
   cout<<res;
   return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int m,n;
int a[N],b[N];

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    cin>>a[i];

    for(int i=1;i<=m;i++)
    cin>>b[i];

   sort(a+1,a+1+n);

   long long res=0;

   for(int i=1;i<=m;i++)
   {
      int l=1,r=n;
      int mid;

      while(l<=r)
     {
      mid=(l+r)/2;   
      if(a[mid]<b[i])
      l=mid+1;
      else
      r=mid-1;
     }
     if(b[i]<=a[1]) res+=a[1]-b[i];
     else
     res+=min(abs(a[l]-b[i]),abs(a[r]-b[i]));
   }
   cout<<res;
   return 0;
}

by syr1125 @ 2023-07-30 15:44:36

CU BALL 我也分不清


by lizhu0han @ 2023-07-31 14:19:21

本蒟蒻认为:是区间的问题


|