TYVJ1463 智商问题【数据结构】【分块】

本文主要是介绍TYVJ1463 智商问题【数据结构】【分块】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述
某个同学又有很多小姊妹了
他喜欢聪明的小姊妹所以经常用神奇的函数来估算小姊妹的智商
他得出了自己所有小姊妹的智商
小姊妹的智商都是非负整数
但是这个同学看到别的同学的小姊妹
也喜欢用神奇的函数估算一下
然后看看这个小姊妹在自己的小姊妹群体中排在第几位…
(这么邪恶的兴趣…)
输入格式
第一行一个整数N 代表小姊妹的个数
第二行N个整数代表这位同学N个小姊妹的智商
接下来若干行每行一个整数
代表这位同学看中的别人的小姊妹的智商
0<=智商<=2^31-1
0<=N<=1000000
输出格式
输出若干行
每行一个整数回答新的小姊妹
在原来小姊妹中智商的排名
测试样例1
输入
5
1 2 3 4 5
1
2
3
4
5
输出
1
2
3
4
5
备注
数据量很大
C语言用scanf输入输出!
另外这个同学的小姊妹群体在这个题中是不会变的~
他会在看完所有别的同学的小姊妹之后…
大家听说过苏格拉底和麦田的故事的吧…
Bob HAN
解题报告
这是一道分块的模板题，恰好做了他练练手。
代码如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e6;
int a[N+5],last[N+5];
int blk,n,cnt,x;
int query(int x)
{if(x>a[n])return n+1;if(x<a[1])return 1;for(int i=1;i<=cnt+1;i++){if(x>last[i-1]&&x<=last[i])//先选出在那个块里边 for(int j=1;j<=blk;j++)//再暴力枚举块的位置 if(a[j+(i-1)*blk]>=x)return j+(i-1)*blk;}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);blk=sqrt(n);//一块的长度 sort(a+1,a+1+n);if(n%blk)cnt=blk;else cnt=blk+1;//一共分出sqrt(n)块或sqrt(n)+1块 for(int i=1;i<=cnt;i++)last[i]=a[i*blk];//存储一个块里边最后的那个数 last[cnt]=a[n];while(~scanf("%d",&x))printf("%d\n",query(x));return 0;
}