首页 > 代码库 > 第三届沈阳航空航天大学校赛（大连海事大学赛）---C: Greater or Lesser （sort）
第三届沈阳航空航天大学校赛（大连海事大学赛）---C: Greater or Lesser （sort）
Greater or Lesser
Time Limit: 2 Sec Memory Limit: 128 MBDescription
Baby A has given you N positive integers, then, he will ask M times. Each query is positive integer x. For each query, please tell Baby A how many positive integers there are lesser than x or greater than x.
Input
Input contains several test cases ending by the end of file. The first line of each test case is two positive integers N and M (1 <= N <= 2 * 10^6, 1 <= M <= 5000). The second line has N positive integers standing for the numbers that baby A has given you. Then M lines follow. Each line has a positive integer standing for a query. Each number will be lesser than 10^8.
Output
For each query, output one line contains two numbers, standing for the number in Baby A‘s set that is lesser and greater than x.
Sample Input
Sample Output
题意：给n个数，有m次询问，每次询问都有一个x，输出在这个序列中，有多少个数比x小，有多少比x大。
分析：先把数组从小到大排个序，然后用lower_bound(a, a+n, key)和upper_bound(a, a+n, key)进行处理，其中lower_bound(a, a+n, key)返回的a数组中第一个比key小的元素的地址，所以我们用lower_bound(a, a+n, key) - a 就得到了比key小的元素个数，同理，upper_bound(a, a+n, key)返回的是a中第一个比key大的元素位置，则(a + n) - upper_bound(a, a+n, key)就得到了a中比key大的元素个数。而且这个速度还是很可观的。
AC代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[2000005];
int main(){
// freopen("in.txt", "r", stdin);
int n, m, p;
while(scanf("%d%d", &n, &m)!=EOF){
memset(a, 0, sizeof(a));
int fo = 0;
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
}
sort(a, a+n); //从小到大排序
for(int i=0; i<m; i++){
scanf("%d", &p);
printf("%d %d\n", lower_bound(a, a+n, p) - a, (a + n) - upper_bound(a, a+n, p)); //求值
}
}
return 0;
}lower_bound(a, a+n, key)和upper_bound(a, a+n, key)对于我这种比较懒的人，还是很好用的^_^
第三届沈阳航空航天大学校赛（大连海事大学赛）---C: Greater or Lesser （sort）