首页 > 代码库 > 【tyvj1463】智商问题 [分块][二分查找]

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

2024-10-21 16:35:39   202人阅读

Background

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

Description

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

InputFormat

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

OutputFormat

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

SampleInput

5

1 2 3 4 5

1

2

3

4

5

SampleOutput

1

2

3

4

5

 

tyvj挂了，交不了

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

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

不如写二分

 1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7  8 const int maxn=100005; 9 10 int n,h;11 int a[maxn],c[maxn],mxnum[(int)sqrt(maxn)+1],mxsite[(int)sqrt(maxn)+1];12 13 int main(){14     freopen("temp.in","r",stdin);15     scanf("%d",&n);16     for(int i=0;i<n;i++)  scanf("%d",&a[i]);17     sort(a,a+n);18     for(int i=0,h=(int)sqrt(n),v=1;i<n;i++){19         c[i]=v;20         if(i==n-1){21             h=v;22             break;23         }24         if((i+1)%h==0)  v++;25     }26     for(int i=n-1;i>=0;i--)27         if(c[i]!=c[i+1]){28             mxnum[c[i]]=a[i];29             mxsite[c[i]]=i;30         }31     int num,site;32     while(scanf("%d",&num)!=NULL){33         site=0;34         for(int i=k;i;i--){35             if(mxnum[i]<=num){36                 site=mxsite[i];37                 break;38             }39         }40         if(site==0){41             puts("1");42         }43         else{44             for(int i=site;i<n;i++)45                 if(num<=a[i]){46                     printf("%d\n",i+1);47                     break;48                 }49             printf("%d\n",n+1);50         }51     }52     return 0;53 }

 

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


联系
我们