二分问题

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=2e5;
   
4. typedef long long ll;
   
5. ll a[N],b[N];
   
6. int n,m;
   
7. int  main()
   
8. {
   
9.     cin>>n>>m;
   
10.     vector<ll>c(n+m);
    
11.     for(int i=0;i<n;i++)
    
12.     {
    
13.         cin>>a[i];
    
14.     }
    
15. 
    
16.     for(int j=0;j<m;j++)
    
17.     {
    
18.         cin>>b[j];
    
19.     }
    
20.     sort(a,a+n);
    
21.     for(int i=0;i<m;i++)
    
22.     {
    
23.         ll ans=b[i],l=-1,r=n-1,cnt=0;
    
24.         while(l<r)
    
25.         {
    
26.             ll mid=(l+r+1)/2;
    
27.             if(a[mid]<=ans)l=mid;
    
28.             else r=mid-1;
    
29.             
    
30.         }
    
31.         if(l>=0)cout<<l+1<<" ";
    
32.         else cout<<"0"<<" ";
    
33. 
    
34.     }
    
35. 
    
36. }
    
37. //直接写超时，所以用二分

复制代码

为什么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。

修复代码如下：

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. using namespace std;
6. int main()
7. {
8.     int n, m;
9.     cin >> n >> m;
11.     vector<int> c(n + m);
12.     for (int i = 0; i < n; i++) {
13.         cin >> c[i];
14.     }
16.     for (int j = 0; j < m; j++) {
17.         cin >> c[n + j];
18.     }
20.     sort(c.begin(), c.end());
22.     for (int i = 0; i < n + m; i++) {
23.         cout << c[i] << " ";
24.     }
25.     cout << endl;
27.     return 0;
28. }

复制代码

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