【kAri OJ】wzt的树

OJ】wzt的树"/>

【kAri OJ】wzt的树

题目描述

改革春风吹满地，中国人民真争气！家庭联产承包责任制以后，全国人民争想发家致富。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型

输出格式

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

输入样例

1
2
1 3
1
2

输出样例

1

分析

先排序，然后二分找出小于等于Xi 的最后一棵树。

代码

#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\n",l);}}return 0;
}

转载于:.html