为什么过不了,找不到异常的地方 1-1 范围查询(Range)
为什么过不了,找不到错误的地方 1-1 范围查询(Range)
数轴上有n个点,对于任一闭区间 [a, b],试计算落在其内的点数。
输入
第一行包括两个整数:点的总数n,查询的次数m。
第二行包含n个数,为各个点的坐标。
以下m行,各包含两个整数:查询区间的左、右边界a和b。
输出
对每次查询,输出落在闭区间[a, b]内点的个数。
输入样例
5 2
1 3 7 9 11
4 6
7 12
输出样例
0
3
限制
0 ≤ n, m ≤ 5×105
对于次查询的区间[a, b],都有a ≤ b
各点的坐标互异
各点的坐标、查询区间的边界a、b,均为不超过10^7的非负整数
时间:2s,内存:256MB
我的代码:
#include<stdio.h>
#include <stdlib.h>
//归并排序---------------
void merge(long int *L,long int lo,long int mi,long int hi)
{
long int i,k,j;
long int * A=L+lo;
long int len_B=mi-lo;
long int * B=(long int *)malloc(len_B*sizeof(long int));//用于临时存储A的前半段
//将A的前半段复制给B
for(i=0;i<len_B;i++)
{
B[i]=A[i];
}
long int len_C=hi-mi;
long int * C=L+mi;//C指向A的后半段
for(i=0,j=0,k=0;j<len_B;)
{
if((k<len_C)&&(C[k]<B[k]))
{
A[i++]=C[k++];
}
if((len_C<=k)||(B[j]<=C[k]))
{
A[i++]=B[j++];
}
}
}
void mergesort(long int *L,long int lo,long int hi)
{//{lo,hi)
if(hi-lo<2)return ;
long int mi=(lo+hi)>>1;
mergesort(L,lo,mi);
mergesort(L,mi,hi);
merge(L,lo,mi,hi);
}
//-------------------------------
long int binsearch(long int * L,long int e,long int lo,long int hi)
{//返回不大于e的元素最大秩
while(lo<hi)
{
long int mi=(hi+lo)>>1;
(e<L[mi])?hi=mi:lo=mi+1;
}
return --lo;
}
int main()
{
long int *L=(long int *)malloc(1000000*sizeof(long int));
long int m,n,i;
scanf("%ld %ld",&n,&m);
for(i=0;i<n;i++)
{
scanf("%ld",&L[i]);
}
mergesort(L,0,n);//先排序
/*
for(i=0;i<n;i++)
{
printf("%ld ",L[i]);
}
printf("\n");
*/
while(m--)
{
long int p1,p2;
long int count=0;
long int min,max;
scanf("%ld %ld",&min,&max);
p1=binsearch(L,min,0,n);
p2=binsearch(L,max,0,n);
// printf("%ld %ld\n",p1,p2);
if(L[p1]==min)count=1;
if(p1!=p2||count)printf("%ld\n",p2-p1+count);
else printf("0\n");
}
return 0;
}
人家通过的代码:
#include <stdio.h>
void quicksort(int R[],int left,int right);
int get_number(int a, int b, int *A, int n);
int binarysearch_small(int a, int *A, int n);
int binarysearch_big(int b, int *A, int n);
int main() {
int n = 0; //number of points
int m = 0; //time of search
scanf("%d %d", &n, &m);
//cin >> n >> m; //first line input
int point[n]; //point array
int a[m]; //left boundary
int b[m]; //right boundary
int i = 0;
for(i = 0;i < n; i++)
{
scanf("%d", &point[i]);
}
quicksort(point, 0, n-1);
for(i=0;i<m;i++)
{
scanf("%d %d", &a[i], &b[i]);
}
for(i=0;i<m;i++)
{
get_number(a[i],b[i], point, n);
}
return 0;
}
void quicksort(int R[],int left,int right)
{
int i=left,j=right;int temp=R[i];
while(i<j) {
while ((R[j]>temp)&&(j>i)) j=j-1;
if (j>i) { R[i]=R[j];i=i+1; }
while ((R[i]<=temp)&&(j>i)) i=i+1;
if (i<j) {R[j]=R[i]; j=j-1; }
}
R[i]=temp;
if (left<i-1) quicksort(R,left,i-1);
if (i+1<right) quicksort(R,i+1,right);
}
int get_number(int a, int b, int *A, int n)
{
if ((a > A[n-1] && b > A[n-1]) || (a < A[0] && b < A[0]))
{
printf("0\n");
//cout << "0" << endl
return 0;
}
a = binarysearch_small(a, A, n);
b = binarysearch_big(b, A, n);
printf("%d\n",b-a+1);
//cout << b-a+1 << endl;
return 0;
}
int binarysearch_small(int a, int *A, int n)
{
int lo = 0;
int hi = n-1;
while(1 < hi - lo)
{
int mi = (lo+hi) >> 1;
a < A[mi] ? hi = mi : lo = mi;
}
return a <= A[lo]? lo : hi;
}
int binarysearch_big(int a, int *A, int n)
{
int lo = 0;
int hi = n-1;
while(1 < hi - lo)
{
int mi = (lo+hi) >> 1;
a < A[mi] ? hi = mi : lo = mi;
}
return a >= A[hi]? hi : lo;
}
------解决思路----------------------
额?你所谓的过不了?是指什么?首先单纯从运行的结果是跟下面的结果是一样的,只不过你的是输入一行,输出一行,而下面的是全部输入完后再打印……
------解决思路----------------------
while(m--)
{
long int p1,p2;
long int count=0;
long int min,max;
scanf("%ld %ld",&min,&max);
p1=binsearch(L,min,0,n);
p2=binsearch(L,max,0,n);
// printf("%ld %ld\n",p1,p2);
if(L[p1]==min)count=1;
if(p1!=p2
------解决思路----------------------
count)printf("%ld\n",p2-p1+count);
else printf("0\n");
}
数轴上有n个点,对于任一闭区间 [a, b],试计算落在其内的点数。
输入
第一行包括两个整数:点的总数n,查询的次数m。
第二行包含n个数,为各个点的坐标。
以下m行,各包含两个整数:查询区间的左、右边界a和b。
输出
对每次查询,输出落在闭区间[a, b]内点的个数。
输入样例
5 2
1 3 7 9 11
4 6
7 12
输出样例
0
3
限制
0 ≤ n, m ≤ 5×105
对于次查询的区间[a, b],都有a ≤ b
各点的坐标互异
各点的坐标、查询区间的边界a、b,均为不超过10^7的非负整数
时间:2s,内存:256MB
我的代码:
#include<stdio.h>
#include <stdlib.h>
//归并排序---------------
void merge(long int *L,long int lo,long int mi,long int hi)
{
long int i,k,j;
long int * A=L+lo;
long int len_B=mi-lo;
long int * B=(long int *)malloc(len_B*sizeof(long int));//用于临时存储A的前半段
//将A的前半段复制给B
for(i=0;i<len_B;i++)
{
B[i]=A[i];
}
long int len_C=hi-mi;
long int * C=L+mi;//C指向A的后半段
for(i=0,j=0,k=0;j<len_B;)
{
if((k<len_C)&&(C[k]<B[k]))
{
A[i++]=C[k++];
}
if((len_C<=k)||(B[j]<=C[k]))
{
A[i++]=B[j++];
}
}
}
void mergesort(long int *L,long int lo,long int hi)
{//{lo,hi)
if(hi-lo<2)return ;
long int mi=(lo+hi)>>1;
mergesort(L,lo,mi);
mergesort(L,mi,hi);
merge(L,lo,mi,hi);
}
//-------------------------------
long int binsearch(long int * L,long int e,long int lo,long int hi)
{//返回不大于e的元素最大秩
while(lo<hi)
{
long int mi=(hi+lo)>>1;
(e<L[mi])?hi=mi:lo=mi+1;
}
return --lo;
}
int main()
{
long int *L=(long int *)malloc(1000000*sizeof(long int));
long int m,n,i;
scanf("%ld %ld",&n,&m);
for(i=0;i<n;i++)
{
scanf("%ld",&L[i]);
}
mergesort(L,0,n);//先排序
/*
for(i=0;i<n;i++)
{
printf("%ld ",L[i]);
}
printf("\n");
*/
while(m--)
{
long int p1,p2;
long int count=0;
long int min,max;
scanf("%ld %ld",&min,&max);
p1=binsearch(L,min,0,n);
p2=binsearch(L,max,0,n);
// printf("%ld %ld\n",p1,p2);
if(L[p1]==min)count=1;
if(p1!=p2||count)printf("%ld\n",p2-p1+count);
else printf("0\n");
}
return 0;
}
人家通过的代码:
#include <stdio.h>
void quicksort(int R[],int left,int right);
int get_number(int a, int b, int *A, int n);
int binarysearch_small(int a, int *A, int n);
int binarysearch_big(int b, int *A, int n);
int main() {
int n = 0; //number of points
int m = 0; //time of search
scanf("%d %d", &n, &m);
//cin >> n >> m; //first line input
int point[n]; //point array
int a[m]; //left boundary
int b[m]; //right boundary
int i = 0;
for(i = 0;i < n; i++)
{
scanf("%d", &point[i]);
}
quicksort(point, 0, n-1);
for(i=0;i<m;i++)
{
scanf("%d %d", &a[i], &b[i]);
}
for(i=0;i<m;i++)
{
get_number(a[i],b[i], point, n);
}
return 0;
}
void quicksort(int R[],int left,int right)
{
int i=left,j=right;int temp=R[i];
while(i<j) {
while ((R[j]>temp)&&(j>i)) j=j-1;
if (j>i) { R[i]=R[j];i=i+1; }
while ((R[i]<=temp)&&(j>i)) i=i+1;
if (i<j) {R[j]=R[i]; j=j-1; }
}
R[i]=temp;
if (left<i-1) quicksort(R,left,i-1);
if (i+1<right) quicksort(R,i+1,right);
}
int get_number(int a, int b, int *A, int n)
{
if ((a > A[n-1] && b > A[n-1]) || (a < A[0] && b < A[0]))
{
printf("0\n");
//cout << "0" << endl
return 0;
}
a = binarysearch_small(a, A, n);
b = binarysearch_big(b, A, n);
printf("%d\n",b-a+1);
//cout << b-a+1 << endl;
return 0;
}
int binarysearch_small(int a, int *A, int n)
{
int lo = 0;
int hi = n-1;
while(1 < hi - lo)
{
int mi = (lo+hi) >> 1;
a < A[mi] ? hi = mi : lo = mi;
}
return a <= A[lo]? lo : hi;
}
int binarysearch_big(int a, int *A, int n)
{
int lo = 0;
int hi = n-1;
while(1 < hi - lo)
{
int mi = (lo+hi) >> 1;
a < A[mi] ? hi = mi : lo = mi;
}
return a >= A[hi]? hi : lo;
}
------解决思路----------------------
额?你所谓的过不了?是指什么?首先单纯从运行的结果是跟下面的结果是一样的,只不过你的是输入一行,输出一行,而下面的是全部输入完后再打印……
------解决思路----------------------
while(m--)
{
long int p1,p2;
long int count=0;
long int min,max;
scanf("%ld %ld",&min,&max);
p1=binsearch(L,min,0,n);
p2=binsearch(L,max,0,n);
// printf("%ld %ld\n",p1,p2);
if(L[p1]==min)count=1;
if(p1!=p2
------解决思路----------------------
count)printf("%ld\n",p2-p1+count);
else printf("0\n");
}
//更改如下
long int p1,p2;
long int count=0;
long int min,max;
while(m--)
{
scanf("%ld %ld",&min,&max);
p1=binsearch(L,min,0,n);
p2=binsearch(L,max,0,n);
// printf("%ld %ld\n",p1,p2);
if(L[p1]==min)count=1;
if(p1!=p2
------解决思路----------------------
count)printf("%ld\n",p2-p1+count);
else printf("0\n");
}