Two pointer 1B

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bạn có \(2\) mảng số nguyên không âm được sắp xếp theo thứ tự không giảm \(a\) gồm \(n\) phần tử và \(b\) gồm \(m\) phần tử.

Mảng \(c\) gồm \(m\) phần tử được xác định như sau:

\(c_i\) = số phần tử trong mảng \(a\) có giá trị nhỏ hơn \(b_i\)

Hãy xác định mảng \(c\)

Constants

\(1 \leq n, m \leq 10^5\)
\(0 \leq a_i, b_i \leq 10^9\)

Example

Test 1

Input

6 7
1 6 9 13 18 18
2 3 8 13 15 21 25

Output

1 1 2 3 4 6 6

Bình luận

#include <bits/stdc++.h>
#define ll long long
const int N=1e5;
using namespace std;
int n,m,a[N+5],b[N+5],c[N+5];
int solve(int a[],int x)
{
    int l=0,r=n-1,res=0;
    while(l<=r)
    {
        int m=(l+r)/2;
        if(a[m]<x)
        {
            res=m+1;
            l=m+1;
        }else r=m-1;
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    cin >> n >> m;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    for(int i=0;i<m;i++)
    {
        cin >> b[i];
    }
    sort(a,a+n);
    for(int i=0;i<m;i++)
    {
        c[i]=solve(a,b[i]);
    }
    for(int i=0;i<m;i++)
    {
        cout << c[i] << ' ';
    }
    return 0;
}

CODE C++ cho ai cần

7

penistone 9:29 a.m. 9 Tháng 10, 2023

Hint

duyệt theo mảng b, tìm vị trí đầu tiên của mảng a mà giá trị lớn hơn hoặc bằng b, in ra vị trí đó trừ 1 (do mảng đã đc sắp xếp nên độ phức tạp chỉ tầm O(n)

-3

hoangminhlqd20 1:04 p.m. 28 Tháng 4, 2023

summary

:)))

0

thachdeptrai 4:40 p.m. 12 Tháng 11, 2021

ai cho mình xin spoiler với ạ

3 phản hồi

-7

hongquanyl1 8:45 p.m. 12 Tháng 10, 2021

vãi Duy Anh

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

0

danh 7:34 p.m. 3 Tháng 8, 2021

\(2^2\)=4

1 phản hồi

-32

dang7rickroll 6:39 p.m. 17 Tháng 6, 2021

ABCXYZ

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.