时间: 1500ms / 空间: 131072KiB / Java类名: Main
背景
各种数据结构帝~
各种小姊妹帝~
各种一遍AC帝~ 来吧！
描述
某个同学又有很多小姊妹了
他喜欢聪明的小姊妹 所以经常用神奇的函数来估算小姊妹的智商
他得出了自己所有小姊妹的智商
小姊妹的智商都是非负整数
但是这个同学看到别的同学的小姊妹
也喜欢用神奇的函数估算一下
然后看看这个小姊妹在自己的小姊妹群体中排在第几位...
(这么邪恶的兴趣...)
输入格式
第一行一个整数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
这题一眼看去就是二分
再看一眼还是二分
再看还是二分
正解也是二分
但是神TM它出现在了分块的PPT里！
于是强行分块，理所当然地T掉了。加了个i+5的跳跃式取值强行卡过。
你问我为什么不二分找区间？要是加了二分，还要分块何用？
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=1000010; 10 const int mxm=3000; 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 // 18 int block,cnt; 19 int L[mxm],R[mxm]; 20 // 21 int n; 22 int a[mxn]; 23 int query(int x){ 24 int i=1; 25 int ans=0; 26 while(i<=cnt){ 27 if(a[R[i+5]]<x && i+5<=cnt){ 28 ans+=R[i+5]-L[i]+1; 29 i+=6; 30 continue; 31 } 32 if(a[R[i]]<x){ 33 ans+=R[i]-L[i]+1; 34 i++; 35 continue; 36 } 37 for(register int j=L[i];j<=R[i];j++){ 38 if(a[j]<x)ans++; 39 } 40 break; 41 } 42 return ans; 43 } 44 int main(){ 45 n=read(); 46 block=sqrt(n); 47 int i,j; 48 for(i=1;i<=n;++i){a[i]=read();} 49 sort(a+1,a+n+1); 50 cnt=(n-1)/block+1; 51 for(i=1;i<=cnt;++i){ 52 L[i]=R[i-1]+1; 53 R[i]=block*i; 54 } 55 R[cnt]=min(block*cnt,n); 56 /* 57 for(i=1;i<=cnt;i++){ 58 printf("test info: %d\n",i); 59 printf(" L:%d R:%d \n",L[i],R[i]); 60 } 61 for(i=1;i<=n;i++)printf("%d ",a[i]);*/ 62 //init 63 int q; 64 while(scanf("%d",&q)!=EOF){ 65 int ans=query(q); 66 printf("%d\n",ans+1); 67 } 68 return 0; 69 }