tyvj1463 智商问题

1463 智商问题

时间: 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

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[1000100];
 5 int main()
 6 {
 7     int n,m;
 8     scanf("%d",&n);
 9     for (int i=1; i<=n; ++i)
10         scanf("%d",&a[i]);
11     sort(a+1,a+n+1);    
12     while (scanf("%d",&m)!=EOF)
13     {
14         if (m>a[n]) printf("%d
",n+1); 
15         else 
16         {
17             int l = 1, r = n;
18             while (l<r)
19             {
20                 int mid = (l+r)>>1;
21                 if (a[mid]<m) l = mid+1;
22                 else r = mid;
23             }
24             printf("%d
",l);
25         }
26     }
27     return 0;
28 }

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,m;
 5 int a[1000100];
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     for (int i=0; i<n; i++) scanf("%d",&a[i]);
10     sort(a,a+n);
11     while (scanf("%d",&m)!=EOF)
12     {
13         int t=lower_bound(a,a+n,m)-a;
14         printf("%d
",t+1);
15     }
16     return 0;
17 }