Educational Codeforces Round 2 B. Queries about less or equal elements(2점)

2084 단어
B. Queries about less or equal elements
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given two arrays of integers a and b. For each element of the second array bj you should find the number of elements in arraya that are less than or equal to the value bj.
Input
The first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the sizes of arrays a and b.
The second line contains n integers — the elements of array a ( - 109 ≤ ai ≤ 109).
The third line contains m integers — the elements of array b ( - 109 ≤ bj ≤ 109).
Output
Print m integers, separated by spaces: the j-th of which is equal to the number of such elements in array a that are less than or equal to the value bj.
Sample test(s)
input
5 4
1 3 5 7 9
6 4 2 8

output
3 2 1 4

input
5 5
1 2 1 2 5
3 1 4 1 5

output
4 2 4 2 5

제목: 시퀀스 A를 주고 시퀀스 B를 주세요. 시퀀스 A에서 Bi보다 작은 수를 구하세요.
사고방식: A 서열을 정렬한 다음 2분 동안 찾기
총결산: 처음에 2점짜리 글씨를 좌절하고 WA를 한 발 썼다...
ac 코드:
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 1000010
#define LL long long
#define ll __int64
#define INF 0xfffffff
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
using namespace std;
ll a[MAXN];
int main()
{
	int n,m;
	int i;
	ll b;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
		scanf("%I64d",&a[i]);
		sort(a+1,a+n+1);
		while(m--)
		{
			scanf("%I64d",&b);
			int high=n,low=1;
			int k=0;
			int bz=0;
			while(low<=high)
			{
				int mid=(low+high)/2;
				if(a[mid]<=b)
				low=mid+1;
				//else if(a[mid]>b)
				else
				high=mid-1;
			}
			printf(m?"%d ":"%d
",low-1); } } return 0; }

좋은 웹페이지 즐겨찾기