求解救！sicily ACM的一道题目，总是说WrongAnswer……
题目：范围统计
Description
Given a list of N numbers and Q queries,for each query given two numbers a,b.You are asked to count how many numbers in the list
that are in the range [a,b].
Input
Input contains multiple testcases.
The first line of input is an Integer T(T <= 10), the number of testcase.
The second line is an integer N(N <= 100000),the number in the list.
Then N integers followed.
The next line is an integer Q(Q <= 10000),the number of query.
For each query there are two interger a,b(a <= b) -- the lower bound and the upper bound accordingly
Output
?For each query ,output one integer that represent how many numbers are in the range [a,b] .
Sample Input
Copy sample input to clipboard
1
10
5 2 4 1 3 9 7 6 8 10
5
4 6
2 7
0 5
-100 100
-100 0
Sample Output
3
6
5
10
0
我的代码：
考虑了数字重复的情况，我能想到的测试用例都试过了，都是对的，但就是Wrong Answer！求解救……
- C/C++ code
#include<iostream>#include<algorithm>using namespace std;int binsearch(int a,int n,int q[],int f){ int left=0,right=n-1,middle; while(right-left>=2) { middle=(left+right)/2; if(a==q[middle]) { if(f==0) { for(int i=middle-1;i>=0;i--) { if(q[i]!=a) { return i+1; } } } if(f==1) { for(int i=middle+1;i<=n-1;i++) { if(q[i]!=a) { return i-1; } } } //return middle; } if(a>q[middle]) left=middle+1; else right=middle-1; } if(f==0) { if(right-left==1) { if(a<=q[left]) { for(int i=left-1;i>=0;i--) { if(a>q[i]) return i+1; } } else if(a>q[left]&&a<=q[right]) { return right; } else if(a>q[right]&&a<=q[right+1]) return right+1; } else if(left==right) { if(a<=q[left]) { for(int i=left-1;i>=0;i--) { if(a>q[i]) return i+1; } } else if(a>q[left]&&a<=q[left+1]) return left+1; } } else if(f==1) { if(right-left==1) { if(a<q[left]) return left-1; else if(a>=q[left]&&a<q[right]) return left; else if(a>=q[right]) { for(int i=right+1;i<=n-1;i++) { if(a<q[i]) return i-1; } } } else if(left==right) { if(a<q[left]) return left-1; else if(a>=q[left]) { for(int i=left+1;i<=n-1;i++) { if(a<q[i]) return i-1; } } } }}int main(){ int t,n,m,c,d; cin>>t; for(int i=0;i<t;i++) { cin>>n; int *q=new int[n]; for(int l=0;l<n;l++) { cin>>q[l]; } sort(q,q+n); //for(int i=0;i<n;i++) //cout<<q[i]<<" "; cin>>m; int *count=new int[m]; int a,b; for(int k=0;k<m;k++) { cin>>a>>b; if(b<q[0]||a>q[n-1]) { //count[k]=0; cout<<0<<endl; continue; } else if(a!=b&&(b==q[0]||a==q[n-1])) { //count[k]=1; cout<<1<<endl; continue; } else if(a<=q[0]&&b>=q[0]) { c=0; d=binsearch(b,n,q,1); } else if(a<=q[0]&&b>=q[n-1]) { c=0; d=n-1; } else if(a>=q[0]&&b<=q[n-1]) { c=binsearch(a,n,q,0); d=binsearch(b,n,q,1); } else if(a>=q[0]&&b>=q[n-1]) { c=binsearch(a,n,q,0); d=n-1; } //count[k]=d-c+1; cout<<d-c+1<<endl; } //for(int i=0;i<m;i++) //cout<<count[i]<<endl; } return 0;}
[解决办法]
设有如下输入：
1
2
10 10
1
10 10
LZ程序中以下代码：
else if(b==q[0]||a==q[n-1])
{
//count[k]=1;
cout<<1<<endl;
continue;
}
将输出1。正确结果应该是2吧，因此这段代码好像不能用。
再有，VS2005对函数binsearch提出警告：
warning C4715: 'binsearch' : not all control paths return a value
请考虑是否遗漏：
else return ...
[解决办法]
我搞混了。2楼例子是针对你的另一个帖子：
http://topic.csdn.net/u/20120429/09/fd1b658e-04a7-4a51-9edf-70e17a837cdc.html?45183
对于这个帖子的代码，请试以下例子：
1
2
10 10
1
10 11
[解决办法]
soj上有这题么？地址？
另外，感觉写太复杂了，应该对主数组排序后，用lower_bound和high_bound找到上下界，整个数组大小减去这个范围即可。