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=e6;
int a[N+],last[N+];
int blk,n,cnt,x;
int query(int x)
{
    if(x>a[n])return n+;
    if(x<a[])return ;
    for(int i=;i<=cnt+;i++)
    {
        if(x>last[i-]&&x<=last[i])//先选出在那个块里边 
        for(int j=;j<=blk;j++)//再暴力枚举块的位置 
        if(a[j+(i-)*blk]>=x)return j+(i-)*blk;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    scanf("%d",&a[i]);
    blk=sqrt(n);//一块的长度 
    sort(a+,a++n);
    if(n%blk)cnt=blk;
    else cnt=blk+;//一共分出sqrt(n)块或sqrt(n)+块 
    for(int i=;i<=cnt;i++)
    last[i]=a[i*blk];//存储一个块里边最后的那个数 
    last[cnt]=a[n];
    while(~scanf("%d",&x))
    printf("%d\n",query(x));
    return ;
}