Hoán Đổi
Đề bài
Bạn được cho hai mảng số nguyên dương $a$ và $b$, mỗi mảng có độ dài $n$. Bạn có thể thực hiện phép toán sau đây bao nhiêu lần tuỳ ý (có thể là 0 lần):
- Chọn một chỉ số $i$ $(1 \le i \le n)$ và hoán đổi giá trị $a[i]$ với $b[i]$.
Mục tiêu: tìm giá trị nhỏ nhất có thể của biểu thức $\max(a[1], a[2], \ldots, a[n]) \times \max(b[1], b[2], \ldots, b[n])$ sau khi đã thực hiện các phép hoán đổi.
Input: dòng đầu tiên chứa một số nguyên $t$ $(1 \le t \le 10^6)$ – số lượng bộ test. Với mỗi bộ test:
- Dòng thứ nhất chứa một số nguyên $n$ $(1 \le n \le 10^6)$ – độ dài của hai mảng.
- Dòng thứ hai chứa $n$ số nguyên $a[1], a[2], \ldots, a[n]$ $(1 \le a[i] \le 10^4)$.
- Dòng thứ ba chứa $n$ số nguyên $b[1], b[2], \ldots, b[n]$ $(1 \le b[i] \le 10^4)$.
Dữ liệu đảm bảo tổng giá trị $n$ trên toàn bộ test không vượt quá $10^6$.
Output: với mỗi bộ test, in ra một số nguyên duy nhất: giá trị nhỏ nhất có thể của tích hai giá trị lớn nhất như đã mô tả.
Subtask: 50% số test đầu tiên có $1 \le t, n \le 10^2$; 50% số test còn lại không có giới hạn gì thêm.
3
6
1 2 6 5 1 2
3 4 3 2 2 5
3
3 3 3
3 3 3
2
1 2
2 118
9
2Giải thích ví dụ:
- Test 1: có thể hoán đổi tại các vị trí $i = 2$ và $i = 6$. Khi đó mảng $a$ trở thành $[1, 4, 6, 5, 1, 5]$, giá trị lớn nhất là 6; mảng $b$ trở thành $[3, 2, 3, 2, 2, 2]$, giá trị lớn nhất là 3. Kết quả $= 6 \times 3 = 18$.
- Test 2: các mảng đã giống nhau, không thể thay đổi. Kết quả $= 3 \times 3 = 9$.
- Test 3: có thể hoán đổi tại vị trí $i = 1$. Khi đó $a = [2, 2]$, max $= 2$; $b = [1, 1]$, max $= 1$. Kết quả $= 2 \times 1 = 2$.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm phần hướng dẫn để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Chúc các bạn học tốt và gặt hái nhiều thành công.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngTham lam: dồn hết số lớn về một mảng
Tóm tắt: cho 2 mảng $a, b$ cùng số lượng phần tử, ta có thể đổi chỗ cặp phần tử cùng vị trí $a[i]$ và $b[i]$ cho nhau, bao nhiêu cặp cũng được. Tìm tích 2 phần tử lớn nhất của 2 mảng sao cho tích này nhỏ nhất có thể.
Đọc đề thấy "đáp án phải nhỏ nhất" là thấy mùi tham lam ngay 😄. Nhìn ví dụ 1: ban đầu max của 2 mảng là 6 và 5, tích 30. Sau vài phép đổi chỗ thì max của mảng $b$ chỉ còn 3, tích 18.
Vì sao không thể tốt hơn? Xét cặp có số nhỏ hơn lớn nhất (gọi giá trị đó là $m$): hai số của cặp này nằm ở hai mảng khác nhau và đều $\ge m$, nên cả hai mảng đều có max $\ge m$. Một mảng lại chắc chắn chứa số lớn nhất $M$. Vậy tích luôn $\ge M \times m$, và cách dồn ở trên đạt đúng $M \times m$.
Minh hoạChạy từng cặp
Em nhập 2 mảng cùng độ dài (tối đa 12 phần tử) rồi bấm Tiếp:
Cách 1Đổi chỗ rồi sắp xếp – O(N log N)
Có rất nhiều cách cài đặt. Ví dụ: chạy một lượt, nếu a[i] < b[i] thì đổi chỗ tụi nó để mảng $a$ chứa số lớn, $b$ chứa số nhỏ ở từng vị trí. Xong thì tìm phần tử lớn nhất của $a$ và $b$ rồi nhân lại. Để tìm phần tử lớn nhất có thể dùng luôn hàm sort, 2 thằng cuối cùng của mỗi mảng chính là 2 thằng lớn nhất.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6;
int a[MAX + 5], b[MAX + 5];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
cin >> b[i];
if(a[i] < b[i]){
swap(a[i], b[i]);
}
}
sort(a, a + n);
sort(b, b + n);
cout << a[n - 1] * b[n - 1] << endl;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0]); pos = 1
out = []
for _ in range(t):
n = int(data[pos]); pos += 1
a = list(map(int, data[pos:pos + n])); pos += n
b = list(map(int, data[pos:pos + n])); pos += n
for i in range(n):
if a[i] < b[i]:
a[i], b[i] = b[i], a[i] # dồn số lớn hơn của mỗi cặp về mảng a
a.sort()
b.sort()
out.append(a[-1] * b[-1])
print('\n'.join(map(str, out)))
main()- Mỗi lần đọc xong
b[i]là có đủ dữ liệu để so sánh vớia[i]đã đọc trước đó, đổi chỗ luôn nếu cần, khỏi mất công làm thêm 1 vòng lặp. - Hàm
swapcó sẵn trong C++, gọi ra dùng cho nhanh. - Hàm
sortcó sẵn trong STL, độ phức tạp luôn đảm bảo $O(N \log N)$.
Độ phức tạp: $O(2N)$ đọc 2 mảng cộng $O(2N \log N)$ sắp xếp, tổng quát là $O(N \log N)$ mỗi bộ test. Với tổng $n$ tối đa $10^6$ thì vẫn qua, nhưng bản chất để tìm số lớn nhất ta đâu cần sắp xếp làm gì!
Cách 2Tìm max ngay khi đọc – O(N)
Chỉ cần duyệt một lượt là tìm được số lớn nhất, $O(N)$. Cũng không cần 2 vòng lặp vì 2 mảng có cùng $N$ phần tử; thậm chí tận dụng luôn vòng lặp đọc mảng $b$. Và cũng không cần đổi chỗ gì hết: tạo 2 biến maxA, maxB, với mỗi cặp thì maxA cập nhật bằng số lớn hơn của cặp, maxB cập nhật bằng số nhỏ hơn của cặp.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6;
int a[MAX + 5], b[MAX + 5];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int maxA = 0, maxB = 0;
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
cin >> b[i];
maxA = max(maxA, max(a[i], b[i]));
maxB = max(maxB, min(a[i], b[i]));
}
cout << maxA * maxB << endl;
}
return 0;
}- Khởi tạo
maxA = maxB = 0: giá trị nhỏ nhất có thể để lần so sánh đầu tiên phần tử nào cũng lớn hơn và được cập nhật vào. Vì đề cho $a[i], b[i] \ge 1$ nên khởi tạo 0 là đảm bảo. - Hàm
max(a, b)trả về giá trị lớn hơn,min(a, b)trả về giá trị nhỏ hơn, dùng cho code gọn thay vì viếtif.
Thực ra muốn tối ưu thêm về bộ nhớ thì chẳng cần mảng $b$: giá trị b[i] đọc vào xong là so sánh rồi bỏ, nên chỉ cần một biến $x$:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6;
int a[MAX + 5];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int maxA = 0, maxB = 0;
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
int x;
cin >> x;
maxA = max(maxA, max(a[i], x));
maxB = max(maxB, min(a[i], x));
}
cout << maxA * maxB << endl;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0]); pos = 1
out = []
for _ in range(t):
n = int(data[pos]); pos += 1
a = data[pos:pos + n]; pos += n
b = data[pos:pos + n]; pos += n
maxA = maxB = 0
for x, y in zip(map(int, a), map(int, b)):
if x < y:
x, y = y, x
if x > maxA: maxA = x # số lớn của cặp dồn về mảng a
if y > maxB: maxB = y # số nhỏ của cặp nằm ở mảng b
out.append(maxA * maxB)
print('\n'.join(map(str, out)))
main()endl vừa xuống dòng vừa đẩy (flush) dữ liệu ra ngay, gọi tới $10^6$ lần có thể làm chậm chương trình. Các bạn có thể thay endl bằng '\n' cho an toàn.
Nhận xét
Đăng nhận xét