Bài toán: Cho dãy số a (m phần tử), dãy số b (n phần tử). Tìm giá trị của ai + bj nhỏ nhất. Đưa giá trị nhỏ nhất đó ra màn hình.
Để tìm giá trị nhỏ nhất của tổng ai + bj, ta có thể sắp xếp cả hai dãy số a và b theo thứ tự tăng dần. Sau đó, ta sẽ duyệt qua từng cặp phần tử a[i] và b[j], tính tổng và so sánh với giá trị nhỏ nhất hiện tại. Nếu tổng này nhỏ hơn giá trị nhỏ nhất hiện tại, ta cập nhật giá trị nhỏ nhất. Quá trình này tiếp tục cho đến khi đã duyệt qua tất cả các cặp phần tử a[i] và b[j].
Dưới đây là một ví dụ cụ thể về cách thực hiện thuật toán trên Python:
def find_minimum_sum(a, b):
# Sắp xếp cả hai dãy số theo thứ tự tăng dần
a.sort()
b.sort()
# Khởi tạo giá trị nhỏ nhất ban đầu là vô cùng lớn
min_sum = float('inf')
# Duyệt qua từng cặp phần tử a[i] và b[j]
i = 0
j = 0
while i < len(a) and j < len(b):
# Tính tổng của a[i] và b[j]
current_sum = a[i] + b[j]
# So sánh với giá trị nhỏ nhất hiện tại
if current_sum < min_sum:
min_sum = current_sum
# Di chuyển vị trí của i hoặc j tùy thuộc vào giá trị nhỏ hơn
if a[i] < b[j]:
i += 1
else:
j += 1
return min_sum
# Ví dụ minh họa
a = [1, 3, 5]
b = [2, 4, 6]
minimum_sum = find_minimum_sum(a, b)
print(minimum_sum) # Kết quả: 3 (tổng nhỏ nhất là 1 + 2)
Thêm yêu cầu đọc và ghi tệp .INP và .OUT như các đề thi học sinh giỏi
def find_minimum_sum(a, b):
a.sort()
b.sort()
min_sum = float('inf')
i = 0
j = 0
while i < len(a) and j < len(b):
current_sum = a[i] + b[j]
if current_sum < min_sum:
min_sum = current_sum
if a[i] < b[j]:
i += 1
else:
j += 1
return min_sum
with open("MINARR.INP", "r") as fi:
x = fi.readline().split()
n, m = int(x[0]), int(x[1])
a = fi.readline().split()
a = list(map(int, a))
b = fi.readline().split()
b = list(map(int, b))
minimum_sum = find_minimum_sum(a, b)
with open("MINARR.OUT", "w") as fo:
fo.write(str(minimum_sum))