【kAri OJ】wzt的树

时间限制 1000 ms 内存限制 65536 KB

题目描述

改革春风吹满地，中国人民真争气！家庭联产承包责任制以后，全国人民争想发家致富。wzt于是包了一个山头来种植金丝楠木，花了好几年种了

N

棵树，每棵高度为

Hi

 mm。今年终于有人上门收购了（跪求了半天）！！

一共来了

Q

个厂家要求采购树木，每家都对树的高度有各自要求，必须高于

Xi

 mm。这可把wzt难倒了，这么多的树可怎么统计啊！于是找到了机智的S菊苣，希望知道自己手头还囤积了多少棵不符合此厂家要求的树。

S菊苣实在太忙了，于是麻烦你编程来计算一下

输入格式

第一行是case数

T (T ≤20)

每个case，首先输入树木的数量

N (N ≤50000)

然后输入每颗树的高度

Hi

。 

之后输入厂家的数量

Q (Q ≤50000)

然后输入每个厂家对树木的要求

Xi

.

Hi

和

Xi

都为int型

输出格式

针对每个询问，输出一行相对应的结果。

输入样例

代码语言：javascript复制

1
2
1 3
1
2

输出样例

代码语言：javascript复制

1

分析

先排序，然后二分找出小于等于

Xi 的最后一棵树。

代码

代码语言：javascript复制

#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("%dn",l);
        }
    }
    return 0;
}

case int

0 人点赞