【tyvj1463】智商问题 [分块][二分查找]

2022-11-10 07:21:46

Background

各种数据结构帝~
各种小姊妹帝~
各种一遍AC帝~ 来吧！

Description

某个同学又有很多小姊妹了
他喜欢聪明的小姊妹所以经常用神奇的函数来估算小姊妹的智商
他得出了自己所有小姊妹的智商
小姊妹的智商都是非负整数
但是这个同学看到别的同学的小姊妹
也喜欢用神奇的函数估算一下
然后看看这个小姊妹在自己的小姊妹群体中排在第几位…
(这么邪恶的兴趣…)

InputFormat

第一行一个整数N 代表小姊妹的个数
第二行N个整数代表这位同学N个小姊妹的智商
接下来若干行每行一个整数
代表这位同学看中的别人的小姊妹的智商
0<=智商<=2^31-1
0<=N<=1000000

OutputFormat

输出若干行
每行一个整数回答新的小姊妹
在原来小姊妹中智商的排名

SampleInput

1 2 3 4 5

SampleOutput

tyvj挂了，交不了

随便写了一个代码，细节大概是错了吧。

练习建立分块而已。。。。QwQ

不如写二分

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 int n,h;

 int a[maxn],c[maxn],mxnum[(int)sqrt(maxn)+],mxsite[(int)sqrt(maxn)+];

 int main(){

     freopen("temp.in","r",stdin);

     scanf("%d",&n);

     for(int i=;i<n;i++)  scanf("%d",&a[i]);

     sort(a,a+n);

     for(int i=,h=(int)sqrt(n),v=;i<n;i++){

         c[i]=v;

         if(i==n-){

             h=v;

             break;

         }

         if((i+)%h==)  v++;

     }

     for(int i=n-;i>=;i--)

         if(c[i]!=c[i+]){

             mxnum[c[i]]=a[i];

             mxsite[c[i]]=i;

         }

     int num,site;

     while(scanf("%d",&num)!=NULL){

         site=;

         for(int i=k;i;i--){

             if(mxnum[i]<=num){

                 site=mxsite[i];

                 break;

             }

         }

         if(site==){

             puts("");

         }

         else{

             for(int i=site;i<n;i++)

                 if(num<=a[i]){

                     printf("%d\n",i+);

                     break;

                 }

             printf("%d\n",n+);

         }

     }

     return ;

 }

码农公寓