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 ;
}