二分问题

lsmCC

#include <bits/stdc++.h>
using namespace std;
const int N=2e5;
typedef long long ll;
ll a[N],b[N];
int n,m;
int  main()
{
    cin>>n>>m;
    vector<ll>c(n+m);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }

    for(int j=0;j<m;j++)
    {
        cin>>b[j];
    }
    sort(a,a+n);
    for(int i=0;i<m;i++)
    {
        ll ans=b[i],l=-1,r=n-1,cnt=0;
        while(l<r)
        {
            ll mid=(l+r+1)/2;
            if(a[mid]<=ans)l=mid;
            else r=mid-1;
            
        }
        if(l>=0)cout<<l+1<<" ";
        else cout<<"0"<<" ";

    }

}
//直接写超时，所以用二分

为什么l要从-1开始呢，从0开始就是错误的，为什么有的l从0开始就是对的

FishC_GPT

这段代码实现的是二分问题。首先，从输入中读取了两个整数n和m。然后，创建了一个长度为n+m的vector（注意代码中的调用应该是vector<int> c(n+m)）。接下来，通过for循环依次读取了n个整数，并将其存入数组a中。再次通过for循环读取了m个整数，并存入数组b中。最后，对数组a进行排序。

但是代码中存在一些问题。首先，在输入中读取元素时，应使用for循环从0到n-1的范围，而不是从1开始。其次，sort函数的参数应该是数组a的起始位置和结束位置，即a和a+n。

修复代码如下：

#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){    int n, m;    cin >> n >> m;    vector<int> c(n + m);    for (int i = 0; i < n; i++) {        cin >> c[i];    }    for (int j = 0; j < m; j++) {        cin >> c[n + j];    }    sort(c.begin(), c.end());    for (int i = 0; i < n + m; i++) {        cout << c[i] << " ";    }    cout << endl;    return 0;}

这样，代码就能够正确地读取元素、排序并输出结果了。
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。