Trung Bình Cộng
Đề bài
Cho dãy số nguyên $A$ gồm $N$ phần tử $A_1, A_2, \ldots, A_N$ và một số nguyên $T$. Tìm bộ ba số $a_i, a_j, a_k$ $(1 \le i < j < k \le N)$ có chênh lệch giữa trung bình cộng của ba số này và $T$ là nhỏ nhất. Nếu có nhiều bộ có cùng chênh lệch, hãy chọn một bộ số có tổng lớn nhất.
Dữ liệu: vào từ thiết bị vào chuẩn gồm hai dòng:
- Dòng đầu tiên gồm hai số nguyên $N$ và $T$ $(3 \le N \le 5000;\ |T| \le 10^9)$;
- Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$ $(|A_i| \le 10^9,\ 1 \le i \le N)$.
Kết quả: ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng của ba số tìm được.
Ràng buộc:
- 40% số test tương ứng với 40% số điểm có $N \le 10$;
- 30% số test khác tương ứng với 30% số điểm có $N \le 100$;
- 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.
4 0
-2 3 1 01Giải thích ví dụ: trung bình cộng của các bộ 3 số là:
| Bộ ba | Tổng | Trung bình cộng | |TBC − T| | |Tổng − 3T| | |
|---|---|---|---|---|---|
| (-2, 3, 1) | 2 | 0.667 | 0.667 | 2 | |
| (-2, 3, 0) | 1 | 0.333 | 0.333 | 1 | ✔ chọn |
| (-2, 1, 0) | -1 | -0.333 | 0.333 | 1 | |
| (3, 1, 0) | 4 | 1.333 | 1.333 | 4 |
Hai bộ $(-2, 3, 0)$ và $(-2, 1, 0)$ cùng lệch $0.333$ so với $T = 0$, chọn bộ có tổng lớn hơn là $(-2, 3, 0)$, tổng bằng $1$.
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 và kèm thêm đó là toàn bộ tin nhắn của mình với em ấy, để 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:
Cẩn thậnSai số của số thực
Ok em, thì trước tiên á, bài Trung Bình Cộng đó anh phải nói rõ chỗ này: nếu như bạn nào mà làm theo đúng quy tắc của bài, tức là cộng 3 số lại chia 3, tức là đã phải xử lý trên số thực, thì điều đó vẫn được nhưng khả năng sẽ rủi ro không tốt. Tại vì sao? Vì số thực thì luôn có sai số, nếu có thể tránh xử lý trên số thực thì nên tránh, còn số nguyên thì không bị sai số. Nhưng nếu em chọn xử lý trên số thực cho bài đó thì vẫn được, có điều phải biết cách.
Để anh cho em xem 1 ví dụ về sai số của số thực sẽ làm bài toán bị sai nếu em không chủ động kiểm soát. Hãy thử nhìn đoạn code sau đây:
Code ví dụ: so sánh 2 số thực bằng ==
#include <bits/stdc++.h>
using namespace std;
int main(){
double x = 4 - 10.0/3;
double y = 14.0/3 - 4;
if(x == y){
cout << "x == y";
}
else{
cout << "x != y";
}
return 0;
}x = 4 - 10.0 / 3
y = 14.0 / 3 - 4
if x == y:
print("x == y")
else:
print("x != y")Em thử tính máy tính xem, rõ ràng $x$ và $y$ đều bằng nhau, cụ thể là bằng $0.66666666666666666666666666666667$. Nhưng em thử chạy đoạn code trên thì nó sẽ in ra x != y. Bấm Tự chạy ở khung bên dưới để thấy giá trị thật sự máy tính lưu trong $x$ và $y$ nhé:
Vậy em có biết cách xử lý tình huống đó sao cho nó in ra được là x == y không? Đó là phải xét cho nó chấp nhận có sai số bằng cách như sau:
Code ví dụ: so sánh có chấp nhận sai số
#include <bits/stdc++.h>
using namespace std;
int main(){
double x = 4 - 10.0/3;
double y = 14.0/3 - 4;
if(fabs(x - y) <= 0.001){
cout << "x == y";
}
else{
cout << "x != y";
}
return 0;
}import math
x = 4 - 10.0 / 3
y = 14.0 / 3 - 4
if math.fabs(x - y) <= 0.001:
print("x == y")
else:
print("x != y")fabs là hàm tính trị tuyệt đối số thực và <= 0.001 có nghĩa là ta cho phép sai số là $\frac{1}{1000}$ nha, em thử chạy lại đoạn code đó đi, giờ đây nó sẽ in ra x == y.
double dưới dạng nhị phân với khoảng 15–17 chữ số có nghĩa. Số $\frac{10}{3}$ hay $\frac{14}{3}$ là số thập phân vô hạn, nên bị làm tròn ngay khi lưu. Hai phép tính khác nhau làm tròn ở hai chỗ khác nhau, nên kết quả lệch nhau ở chữ số cuối cùng (khoảng $4 \cdot 10^{-16}$). So sánh == thì đòi bằng nhau tuyệt đối đến từng bit nên trả về sai.Ý tưởngNhân 3 để chỉ làm việc với số nguyên
Quay lại bài Trung Bình Cộng: ví dụ như bài đó ta hoàn toàn không cần xử lý trên số thực mà chỉ cần xử lý trên số nguyên, bằng cách thay vì cộng lại chia 3 thì em nhân 3 lên cho bên kia:
(vì $\left|\frac{S}{3} - T\right| = \frac{|S - 3T|}{3}$, chia cho cùng một số 3 thì thứ tự lớn nhỏ không đổi). Nên bài đó sẽ quy về: tìm 3 số sao cho tổng của tụi nó gần giá trị $3 \cdot T$ nhất, em ok đúng không?
Thì 3 số đó em có thể chọn ở vị trí bất kỳ, miễn phải đảm bảo 3 vị trí chọn khác nhau, có nghĩa là không có 1 vị trí nào mà bị chọn lặp lại. Tóm lại là chọn đủ 3 số ra và hãy chọn làm sao để tổng 3 số đó gần với giá trị $3 \cdot T$ nhất; nếu có nhiều bộ 3 số có chênh lệch với $3 \cdot T$ bằng nhau thì chọn bộ 3 số có tổng lớn nhất, và kết quả cần in ra tổng của bộ 3 số đó. Với ví dụ đề, đặt các tổng lên trục số là thấy ngay:
int (khoảng $2.1 \cdot 10^9$). Nên trong code anh để hết là long long.Cách 1Vét cạn 3 vòng for – O(N³) – 70% điểm
Khi định hình được vấn đề thì nếu theo cách vét cạn sẽ có 3 for lồng nhau, tức là độ phức tạp có thể thấy là $O(N^3)$ rồi đó. Code vét cạn này mình viết thêm để các bạn dễ hình dung (và cũng để dùng làm code đối chứng khi kiểm tra cách tối ưu):
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, t;
cin >> n >> t;
t *= 3;
vector<long long> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
long long Min = LLONG_MAX, Max = LLONG_MIN;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
for(int k = j + 1; k < n; ++k){
long long sum = a[i] + a[j] + a[k];
long long distan = abs(sum - t);
if(distan < Min || (distan == Min && sum > Max)){
Min = distan;
Max = sum;
}
}
}
}
cout << Max;
return 0;
}import sys
data = sys.stdin.read().split()
n, t = int(data[0]), int(data[1]) * 3
a = list(map(int, data[2:2 + n]))
Min = Max = None
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
s = a[i] + a[j] + a[k]
d = abs(s - t)
if Min is None or d < Min or (d == Min and s > Max):
Min, Max = d, s
print(Max)Mà bài này $O(N^3)$ sẽ không thể AC được vì đề cho $N$ tối đa $5000$, thì $5000^3 = 125 \cdot 10^9$, đã vượt quá ngưỡng giới hạn 1 giây là $10^8$ thôi nên chắc chắn sẽ bị TLE. Cách này chỉ ăn được 2 subtask đầu ($N \le 100$ thì $100^3 = 10^6$ phép, rất nhanh), tức là 70% điểm.
Cách 2Sắp xếp + hai con trỏ – O(N²) – AC
Muốn AC được thì phải giảm độ phức tạp xuống, cụ thể bài này có thể giải quyết với độ phức tạp $O(N^2)$ bằng kỹ thuật two pointers (2 con trỏ) em nha. Thì $5000^2 = 25 \cdot 10^6$, nhỏ hơn ngưỡng $10^8$ nên sẽ không sợ bị TLE nha.
Thì em sẽ thấy là mấu chốt của các bài cần dùng 2 con trỏ đó là dãy số phải có thứ tự, nên bước đầu tiên ta sẽ sort dãy số tăng dần chẳng hạn. Sau đó em phải hình dung: nếu theo cách vét cạn thì 3 for lồng nhau tức là $O(N^3)$, thì với 2 con trỏ nó sẽ giảm bớt đi được 1 for chỉ còn $O(N^2)$. Thì phải tưởng tượng $O(N^2)$ là thế nào? Tức là 2 cái vòng lặp lồng nhau.
Vậy đầu tiên sẽ có 1 vòng lặp for i để lặp qua lần lượt từng phần tử a[i], rồi với mỗi phần tử a[i] đó ta sẽ tìm ra 2 vị trí a[l], a[r] với ràng buộc $i < l < r$ sao cho tổng a[i] + a[l] + a[r] gần với $3 \cdot T$ nhất:
- Đầu tiên cứ cho
l = i + 1vàr = n - 1, tính tổng 3 thằng, tính khoảng cách tổng đó với $3 \cdot T$. - Nếu khoảng cách mà nhỏ hơn
Min(là giá trị đại diện lưu khoảng cách nhỏ nhất đã tìm được) thì cập nhật lạiMin= khoảng cách mới và cập nhậtMax = sum(Maxlà giá trị đáp án, tổng lớn nhất của bộ 3 số thoả). - Còn nếu khoảng cách mà bằng
Minthì so sánh tổng 3 số đó vớiMaxhiện tại, nếu tổng 3 số mới mà lớn hơnMaxthì cập nhật lạiMax= tổng 3 số mới, vì đề yêu cầu nếu có cùng khoảng cách nhỏ nhất thì chọn bộ 3 số có tổng lớn nhất mà.
Rồi thì ta so sánh tổng 3 số với $3 \cdot T$:
l++: rõ ràng ta cần tăng l lên để rút ngắn khoảng cách lại, vì khi đó a[l] sẽ là giá trị mới $\ge$ a[l] trước đó. Chứ em tưởng tượng nếu tổng đang nhỏ hơn $3T$ mà ta lại giảm r-- thì lần tiếp theo xét thằng a[r] mới có giá trị nhỏ hơn so với a[r] lần trước, nó lại càng cách xa cột mốc hơn nữa.Tổng ≥ 3T →
r--: rõ ràng ta cần giảm r để rút ngắn khoảng cách lại, vì khi đó a[r] sẽ là giá trị mới $\le$ a[r] trước đó. Chứ nếu tổng đang $\ge 3T$ mà ta lại tăng l++ thì a[l] mới còn lớn hơn a[l] lần trước, nó lại càng cách xa cột mốc hơn nữa.Đó, cứ như thế thôi. Em nhập $T$ và dãy số rồi bấm Tiếp để xem 2 con trỏ chạy trên dãy đã sắp xếp, cùng trục số so sánh tổng với $3T$:
Anh đưa ý tưởng cụ thể rồi đó, em thử code đi nhé, nếu không ra thì em nhắn anh sẽ cho em tham khảo code hen. Đây là source code của anh theo đúng ý tưởng dùng 2 con trỏ mà anh đã nói ở trên, em xem nhé:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, t;
cin >> n >> t;
t *= 3;
long long a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
long long Min = LLONG_MAX;
long long Max = LLONG_MIN;
sort(a, a + n);
int sz = n - 2;
for(int i = 0; i < sz; ++i){
int l = i + 1, r = n - 1;
while(l < r){
long long sum = a[i] + a[l] + a[r];
long long distan = abs(sum - t);
if(distan < Min){
Min = distan;
Max = sum;
}
else if(distan == Min){
Max = max(Max, sum);
}
if(sum < t){
l++;
}
else{
r--;
}
}
}
cout << Max;
return 0;
}import sys
from math import inf
n, t = map(int, sys.stdin.readline().split())
t *= 3
a = list(map(int, sys.stdin.readline().split()))
Min = inf
Max = -inf
a.sort()
sz = n - 2
for i in range(sz):
l = i + 1
r = n - 1
while l < r:
sum_ = a[i] + a[l] + a[r]
distan = abs(sum_ - t)
if distan < Min:
Min = distan
Max = sum_
elif distan == Min:
Max = max(Max, sum_)
if sum_ < t:
l += 1
else:
r -= 1
print(Max)Vì sao 2 con trỏ không bỏ sót bộ tốt nhất?
Với mỗi $i$ cố định: khi tổng < $3T$ mà ta bỏ a[l] đi (l++), thì mọi cặp (l, r') với r' < r còn lại đều có tổng $\le$ tổng hiện tại < $3T$, tức là đều xa hơn hoặc bằng và tổng nhỏ hơn, không thể tốt hơn bộ vừa xét. Tương tự khi tổng $\ge 3T$ mà bỏ a[r] (r--), mọi cặp (l', r) với l' > l đều có tổng $\ge$ tổng hiện tại $\ge 3T$, xa hơn hoặc bằng. Vì vậy cả bộ gần nhất phía dưới lẫn bộ gần nhất phía trên $3T$ đều được xét tới, nên luật chọn tổng lớn hơn khi hoà vẫn đúng.
Đánh giá độ phức tạp thời gian (Time Complexity)
- Bước đọc dữ liệu từ input: $O(N)$.
- Bước sort: $O(N \log N)$.
- Bước xử lý với kỹ thuật 2 con trỏ: $O(N^2)$ (với mỗi $i$,
lvàrtiến lại gần nhau, tổng cộng tối đa $N$ bước).
⇒ Tổng: $O(N) + O(N \log N) + O(N^2)$, thì theo quy tắc cộng BigO khi có nhiều thành phần cộng với nhau sẽ lấy đại diện thằng lớn nhất, vì thế về mặt tổng quát ta có thể kết luận là $O(N^2)$, và như đã phân tích hồi đầu thì bài này $N$ tối đa $5000$ nên $O(N^2)$ sẽ đủ sức AC nhé.
Nhận xét
Đăng nhận xét