trang chủ / đề bài / distjoin

Phép nối phân tán

Đề bài

Mô tả

Cần thực hiện phép nối hai bảng A và B trong một hệ cơ sở dữ liệu phân tán. Bảng A nằm trên cụm thứ nhất gồm m phân vùng, phân vùng thứ i chứa ai dòng của A. Bảng B nằm trên cụm thứ hai gồm n phân vùng, phân vùng thứ i chứa bi dòng của B.

Mỗi thao tác mạng sao chép một dòng từ một phân vùng bất kỳ sang một phân vùng bất kỳ khác (của cùng cụm hoặc cụm kia). Dòng gốc vẫn được giữ lại, nên một dòng có thể được sao chép tới nhiều phân vùng.

Sau khi thực hiện các thao tác, với mỗi cặp gồm một dòng của A và một dòng của B, phải tồn tại ít nhất một phân vùng chứa cả hai dòng đó. Hãy tìm số thao tác mạng ít nhất.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên m và n.
  • Dòng thứ hai chứa m số nguyên a1,a2,…,am.
  • Dòng thứ ba chứa n số nguyên b1,b2,…,bn.

Dữ liệu ra

In ra một số nguyên là số thao tác mạng ít nhất.

Ràng buộc

  • 1≤m,n≤105
  • 1≤ai,bi≤109

Ví dụ

Input Output Giải thích
2 2
2 6
3 100
11 Chuyển mọi dòng còn lại về phân vùng thứ hai của cụm thứ hai: 2+6+3=11 thao tác.
2 3
10 10
1 1 1
6 Sao chép mỗi dòng của B tới cả hai phân vùng của cụm thứ nhất: 2·3=6 thao tác.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0