学步园

题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1029

题目大意是说给出a数组，对于b中的每一个在a中找出最小范围使得ai<=b<a(i+1)，注意Print a blank line after each test case.这一句话！开始没看到结果WA了，杯具

自敲的二分

#include<iostream><br /> using namespace std;<br /> #include<algorithm></p> <p>int n,m;</p> <p>int find(int *a,int x)<br /> {<br /> int l=0,r=n-1,mid;<br /> if(x<a[0] || a[n-1]<=x)return -1;<br /> while(l<=r)<br /> {<br /> mid=(l+r)/2;<br /> if(a[mid]<=x && a[mid+1]>x)return mid;<br /> if(a[mid]<=x)<br /> l=mid;<br /> else<br /> r=mid;<br /> }<br /> return l;//这里不需要再return了，因为上面肯定可以找到这个区间<br /> }</p> <p>int main()<br /> {<br /> int a[10001];<br /> freopen("a.txt","r",stdin);<br /> while(cin>>n>>m)<br /> {<br /> int i,j;<br /> for(i=0;i<n;i++)<br /> cin>>a[i];<br /> sort(a,a+n);<br /> for(i=0;i<m;i++)<br /> {<br /> int b;<br /> cin>>b;<br /> j=find(a,b);<br /> if(j>=0)<br /> cout<<"["<<a[j]<<","<<a[j+1]<<")"<<endl;<br /> else<br /> cout<<"no such interval/n";<br /> }<br /> cout<<"/n";<br /> }<br /> return 0;<br /> }

stl---lower_bound()

#include<iostream><br /> using namespace std;<br /> #include<algorithm></p> <p>int n,m;</p> <p>int find(int *a,int x)<br /> {<br /> if(x<a[0] || a[n-1]<=x)return -1;<br /> return lower_bound(a,a+n,x)-a;<br /> }</p> <p>int main()<br /> {<br /> int a[10001];<br /> while(cin>>n>>m)<br /> {<br /> int i,j;<br /> for(i=0;i<n;i++)<br /> cin>>a[i];<br /> sort(a,a+n);<br /> for(i=0;i<m;i++)<br /> {<br /> int b;<br /> cin>>b;<br /> j=find(a,b);<br /> if(a[j]!=b)j=j-1;<br /> if(j>=0)<br /> cout<<"["<<a[j]<<","<<a[j+1]<<")"<<endl;<br /> else<br /> cout<<"no such interval/n";<br /> }<br /> cout<<"/n";<br /> }<br /> return 0;<br /> }</p> <p>