【kAri OJ】wzt的树
内存限制 65536 KB
题目描述
改革春风吹满地，中国人民真争气！家庭联产承包责任制以后，全国人民争想发家致富。wzt于是包了一个山头来种植金丝楠木，花了好几年种了i mm。今年终于有人上门收购了（跪求了半天）！！
一共来了i mm。这可把wzt难倒了，这么多的树可怎么统计啊！于是找到了机智的S菊苣，希望知道自己手头还囤积了多少棵不符合此厂家要求的树。
S菊苣实在太忙了，于是麻烦你编程来计算一下
输入格式
第一行是case数)
每个case，首先输入树木的数量)
然后输入每颗树的高度i。
之后输入厂家的数量)
然后输入每个厂家对树木的要求i.
i都为int型
输出格式
针对每个询问，输出一行相对应的结果。
输入样例
1
2
1 3
1
2
输出样例
1分析
先排序，然后二分找出小于等于i 的最后一棵树。
代码
#include<cstdio> #include<algorithm> using namespace std; int t,n,h[50005]= {-1},q,x; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&h[i]); sort(h+1,h+n+1); scanf("%d",&q); for(int i=0; i<q; i++) { scanf("%d",&x); int l=0,r=n,m; while(l<r-1) { m=l+r>>1; if(h[m]<=x) l=m; else r=m; } if(l+1==r&&h[r]<=x)l++; printf("%d ",l); } } return 0; }