SEARCH3 - Tìm kiếm nhị phân 3
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho hai dãy số nguyên ~a_1, a_2, …, a_n~ và ~b_1, b_2, …, b_m~. Với mỗi chỉ số ~i~ ~(1 ≤ i ≤ m)~ hãy tìm sự xuất hiện của ~b_i~ trong dãy ~a_1, a_2, …, a_n~.
Input
- Dòng đầu ghi hai số nguyên dương ~n~ và ~m~;
- Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, …, a_n~;
- Dòng thứ ba ghi ~m~ số nguyên ~b_1, b_2, …, b_m~.
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Giới hạn:
- ~1 ≤ n, m ≤ 10^5; |a_i|, |b_i| ≤ 10^9~.
Output
- Một dòng duy nhất chứa m số nguyên, trong đó số thứ ~i~ ~(1 ≤ i ≤ m)~ là chỉ số ~j~ nhỏ nhất mà ~a_j = b_i~ (nếu tồn tại) và là ~0~ nếu ngược lại. Hai số liên tiếp được ghi cách nhau một dấu cách.
Sample
Input #1
7 5
6 4 7 2 4 1 3
3 1 5 4 8
Output #1
7 6 0 2 0
Problem source: Chuyên Sơn La Online Judge
Bình luận
include<bits/stdc++.h>
define int long long
using namespace std; int n,m,a[1000005],x; map<int,int> vtri; main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; if(vtri[a[i]]==0) vtri[a[i]]=i+1;} for(int i=0;i<m;i++) { cin>>x; cout<<vtri[x]<<" ";}
} code chuẩn
hướng dẫn mọi người: tìm tần số xuất hiện lần đầu các số trong mảng a. Dùng map(C++) hoặc là dict(Python) để lưu giá trị. sau khi tìm số xuất hiện xong thì duyệt 1 vòng lặp for của mảng b. nếu b[i] có trong bảng tần suất thì in ra vị trí của nó. không thì in ra 0
code mẫu
bạn ơi ai, bi <= 10 * 9 ko map dc đâu, bài này dùng sort và tk nhị phân phần tử xh đầu nhé. test case cho 10 * 9 là cách của bạn bị tràn mảng
include<bits/stdc++.h>
using namespace std; int inDex[100001]; void quicksort(long a[], long l, long r) { long key = a[(l + r)/2]; long i = l, j = r; while(i <= j){ while(a[i] < key) ++i; while(a[j] > key) --j; if(i <= j){ if(a[i] != a[j]){ long tm = a[i]; a[i] = a[j]; a[j] = tm; long gn = inDex[i]; inDex[i] = inDex[j]; inDex[j] = gn; ++i; --j; } else{ long tm = a[i]; a[i] = a[j]; a[j] = tm; ++i; --j; } } } if(l < j){ quicksort(a, l, j); } if(i < r){ quicksort(a, i, r); } } int bSearch(long a[], long l, long r, long key) { long dau = l, cuoi = r; while(dau <= cuoi){ long mid = (dau + cuoi)/2; if(a[mid] == key){ int tm = mid - 1; while(a[tm] == key) --tm; return tm + 1; } if(a[mid] > key) cuoi = mid - 1; if(a[mid] < key) dau = mid + 1; } return 0; } int main() { long n, m; cin>>n>>m; inDex[0] = 0; long a[100001], b[100001]; for(long i = 1; i <= n; ++i) { cin>>a[i]; inDex[i] = i; } for(long i = 1; i <= m; ++i){ cin>>b[i]; } quicksort(a, 1, n); for(int i = 1; i <= m; ++i){ cout<<inDex[bSearch(a, 1, n, b[i])]<<" "; }
}
có bạn nào giải bài này chưa cho mình xin code với. Test có vấn đề gì không sao mình toàn bị WA ở test 2.
có 2 cách, 1 là dùng sort+binary_search,2 là dùng map lưu lại giá trị xuất hiện nhỏ nhất của a[i] rồi xuất kq ra thôi