high
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Khôi vừa viết một ứng dụng hẹn hò mang tên Fake love. Ứng dụng đang có \(n\) bạn nữ, \(m\) bạn nam đang sử dụng, biết rằng 2 người nam nữ sẽ chỉ thấy hợp nhau nếu độ chênh lệch cân nặng của họ không vượt quá \(k\). Qua một số thuật toán, ứng dụng của của Khôi sẽ xếp các nam nữ hợp nhau thành các couple. Vì muốn biết ứng dụng của mình đã tối tưu chưa, nên Khôi hỏi bạn có nhiều nhất bao nhiêu couple có thể có (1 nam chỉ có ghép thể với 1 bạn nữ, ngược lại cũng vậy).
Input
- \(n, m, k(1 \leq n, m\leq 2*10^5, 0 \leq k \leq 10^9)\).
- \(n\) số nguyên, \(1 \leq a_i\leq10^9\) cân nặng của các bạn nữ.
- \(m\) số nguyên, \(1 \leq b_i\leq10^9\) cân nặng của các bạn nam.
Output
- số couple.
Example
Test 1
Input
4 3 5
60 45 80 60
30 60 75 Output
2
Bình luận
include <bits/stdc++.h>
using namespace std;
long long n,x,a[1000006],l,kq=1,r,d,t[1000006],ok,k,m,ko;
map<long long,long long> y,z;
map<long long,long long>::iterator it;
int main()
{
freopen("vd.inp","r",stdin);
freopen("vd.out","w",stdout);
cin>>n>>m>>k;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>t[i];
sort(a+1,a+n+1);
sort(t+1,t+m+1);
l=r=1;
while(l<=n && r<=m)
{
ok=abs(a[l]-t[r]);
if(ok<=k)
{
l++;
r++;
d++;
}
else if(a[l]<t[r])l++; else if(ok>k)r++;
}