「JoyOI1463」智商问题
背景 Background
各种数据结构帝~
各种小姊妹帝~
各种一遍AC帝~ 来吧！
描述 Description
某个同学又有很多小姊妹了
他喜欢聪明的小姊妹 所以经常用神奇的函数来估算小姊妹的智商
他得出了自己所有小姊妹的智商
小姊妹的智商都是非负整数
但是这个同学看到别的同学的小姊妹
也喜欢用神奇的函数估算一下
然后看看这个小姊妹在自己的小姊妹群体中排在第几位…
(这么邪恶的兴趣…)
输入格式 InputFormat
第一行一个整数N 代表小姊妹的个数
第二行N个整数 代表这位同学N个小姊妹的智商
接下来若干行 每行一个整数
代表这位同学看中的别人的小姊妹的智商
0<=智商<=2^31-1
0<=N<=1000000
输出格式 OutputFormat
输出若干行
每行一个整数 回答新的小姊妹
在原来小姊妹中智商的排名
数据范围和注释 Hint
数据量很大
C语言用scanf输入输出!
另外 这个同学的小姊妹群体在这个题中是不会变的~
他会在看完所有别的同学的小姊妹之后…
大家听说过 苏格拉底和麦田的故事的吧…
题解
这题是个二分的简单题
不过可以用来练习分块，将a数组排序之后分为√n块，记录一下每一块的最大值
每次询问先√n枚举找到这个数所在的块，再在块内暴力√n个元素
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<cmath> #include<cstdio> #include<iostream> #include<algorithm> #define inf 0x7fffffff #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,t,a[1000005]; int last[1005]; int query(int x) { if(x>a[n])return n+1; if(x<a[1])return 1; for(int i=1;i<=t+1;i++) if(x<=last[i]&&x>last[i-1]) { int b=(i-1)*t; for(int j=1;j<=t;j++) if(a[b+j]>=x)return (b+j); } } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); t=sqrt(n); for(int i=1;i<=t;i++) last[i]=a[t*i]; last[t+1]=a[n]; int x; while(scanf("%d",&x)!=EOF) printf("%d\n",query(x)); return 0; } |
计数器 9787006
OI 课件=>
OI 课件=>
黄学长，为什么我把last数组存成下标，然后每次查询的时候套上a，这样就会T掉一组。
老老实实写二分呗，
。。那我就要练分块。。