完整题目描述:
<span style="font-size:14px;">#include<stdio.h>
int a[100005][2];
int max(int a,int b){return a>b?a:b;}
int main()
{
int n,q,i,x;
while(scanf("%d",&n)!=EOF)//n<=100000
{
for(i=0;i<n;i++) scanf("%d%d",&a[i][0],&a[i][1]);//两个数均大于等于0且小于等于1000000000
scanf("%d",&q);//q<=100000
while(q--)
{
scanf("%d",&x);//0<=x<=1000000000
int ans=-1;
for(i=0;i<n;i++)
{
if(a[i][0]<x) ans=max(ans,a[i][1]);
}
printf("%d\n",ans);
}
}
return 0;
}
</span>
优化以上代码。题目大概是说:给定n个点(xi,yi)。然后q个查询,每个查询是一个a,输出x坐标小于a的最大的y,不存在则输出-1
这道题也是典型的优化>预处理优化的题目,不过这道题是离线处理
这道题的思路其实也很简单。我们只需要运用贪心的思想,一开始的时候声明一个结构体存储每个输入的x和y坐标,然后将输入的所有结构体按照y坐标值降序排序。接下来的一步便是关键步骤。由于是q次查询,我们自然想到先声明一个同样的结构体数组,将所有查询先记录下来(记录在这些结构体数组的x坐标),然后将这q次查询按照x值大小排序(这样的话能够有效的减少重复计算次数)。在这里需要注意的是我们需要将排序的q次查询进行升序排序,然后再开始遍历原来按照y值已经排序好的坐标,每次找到比待查询的x值小的坐标,便将该值对应的y坐标值存储进查询对应的y值坐标,然后内层循环终止,继续找下一个查询对应的y值。这样的话一一遍历过去,直到找到所有查询对应的y坐标值。最后再用原来临时存储的初始输入的查询值x(未排序前),进行二分查找(增加效率),将每次查询的x坐标值对应的y坐标值一一输出即可。
完整的优化源代码如下:
#include<cstdio>
#include<algorithm>
using namespace std;
struct coord
{
int x;
int y;
} a[100005];
coord que[100005]; //用来存储询问的x坐标,再离线处理y坐标
void quick_sort(int left,int right,coord b[],bool flag);
int main()
{
int n,q;
while(scanf("%d",&n)!=EOF)//n<=100000
{
for(int i = 0; i<n; i++) scanf("%d%d",&a[i].x,&a[i].y); //两个数均大于等于0且小于等于1000000000
quick_sort(0,n-1,a,true);
scanf("%d",&q);//q<=100000
coord temp_q[100005];
for(int i = 0;i < q;i++)
{
scanf("%d",&que[i].x); //输入查询的x值
que[i].y = -1;
}
for(int i = 0;i < q;i++)
temp_q[i] = que[i]; //存储查询的初始值
quick_sort(0,q-1,que,false); //将查询的x值按照升序排序
int flag = 0;
for(int j = 0;j < q;j++)
{
for(int i = flag;i < n; i++)
{
if(a[i].x < que[j].x)
{
flag = i; //更新当前扫描到的值
que[j].y = a[i].y;
break;
}
}
}
for(int i = 0;i < q;i++)
{
int mid,low = 0,high = q;
while(low <= high) //二分查找并输出,升序数组中查找
{
mid = (low + high) / 2;
if(que[mid].x > temp_q[i].x) low = mid + 1;
else if(que[mid].x < temp_q[i].x) high = mid - 1;
else if(que[mid].x == temp_q[i].x)
{
printf("%d\n",que[mid].y);
break;
}
}
}
}
return 0;
}
void quick_sort(int left,int right,coord b[],bool flag)
{
int temp,i,j; //用来存储基准数
coord temp_coord = b[left]; //每次都以最左边的数字作为基准数
if(left >= right) return;
i = left;
j = right;
while(i < j)
{
while((i < j && b[j].y <= b[left].y && flag) || (i < j && b[j].x <= b[left].x && !flag))
j--;
while((i < j && b[i].y >= b[left].y && flag) || (i < j && b[i].x >= b[left].x && !flag))
i++;
if(i < j)
{
coord flag = b[j];
b[j] = b[i];
b[i] = flag;
}
}
b[left] = b[i];
b[i] = temp_coord; //基准数归位
quick_sort(left,i - 1,b,flag);
quick_sort(i + 1,right,b,flag); //排序基准数左边和右边的序列
}
如有错误,还请指正,O(∩_∩)O谢谢