Ăn Bánh (cookies)
Đề bài
Ăn bánh
Nhân dịp sinh nhật Vova, cô giáo đã mua $n$ gói bánh quy nhỏ để tổ chức cho bạn ấy, gói bánh thứ $i$ có số lượng bánh là $a[i]$.
Như thường lệ, cô giáo đặt các gói bánh trên bàn theo hàng ngang từ gói bánh thứ nhất đến gói bánh thứ $n$, sau đó các bạn nhỏ ăn bánh ở $k$ gói liên tiếp đầu tiên $(1 \le k \le n - 2)$. Trong số các gói bánh còn lại cô lấy gói bánh ít nhất để mang về làm quà cho con trai yêu quý mình, và tính tổng trung bình các gói bánh còn lại sẽ chia đều cho các bạn nhỏ trong lớp.
Các bạn nhỏ muốn tìm tất cả giá trị $k$ sao cho tổng trung bình các gói bánh còn lại (sau khi cô giáo đã lấy gói nhỏ nhất) đạt giá trị lớn nhất.
Input
- Dòng 1: chứa số nguyên dương $n$ $(3 \le n \le 10^5)$;
- Dòng 2: chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(0 \le a_i \le 10^4;\ i = \overline{1, n})$.
Output
- Một dòng duy nhất chứa các giá trị $k$ (sắp xếp tăng dần) tìm được.
Ràng buộc:
- Có 40 số test ứng với 40 số điểm của bài có $3 \le n \le 10^2$;
- Có 60 số test ứng với 60 số điểm của bài có $10^3 \le n \le 10^5$.
5
3 1 9 2 72Giải thích ví dụ:
- Nếu các bạn nhỏ ăn $k = 1$ gói bánh đầu tiên, còn lại 4 gói là
1 9 2 7, cô giáo sẽ lấy gói bánh1và 3 gói bánh còn lại tính trung bình sẽ là: $(9 + 2 + 7) / 3 = 6$. - Nếu các bạn nhỏ ăn $k = 2$ gói bánh đầu tiên, còn lại 3 gói là
9 2 7, cô giáo sẽ lấy gói bánh2và hai gói bánh còn lại tính trung bình sẽ là $(9 + 7) / 2 = 8$. - Nếu các bạn nhỏ ăn $k = 3$ gói bánh đầu tiên, còn lại 2 gói là
2 7, cô giáo sẽ lấy gói bánh2và một gói bánh còn lại tính trung bình sẽ là $7 / 1 = 7$.
Như vậy: các bạn nhỏ cần ăn $k = 2$ gói bánh đầu tiên để nhận được tổng trung bình các gói bánh còn lại (sau khi cô giáo lấy đi gói ít nhất) lớn nhất bằng $8$.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé, các bạn nào 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:
Link này công khai, bạ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 CLAOJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Làm đúng theo đề – vét cạn O(N²)
Bài này thì làm theo đúng yêu cầu của đề đó là: với mỗi giá trị $K$ từ $1$ đến $N - 2$ thì em duyệt phần còn lại $a_{K+1}, \ldots, a_N$, tìm ra số nhỏ nhất và tổng của chúng, lấy tổng trừ đi thằng nhỏ nhất rồi chia cho số gói còn lại để ra trung bình cộng. Cứ thế tìm ra thằng có trung bình cộng lớn nhất.
Ví dụ $N = 10$ đi ha:
- Khi $K = 1$, thì với 9 phần tử còn lại em phải tính trung bình cộng của 8 thằng (không tính thằng nhỏ nhất).
- Khi $K = 2$, thì với 8 phần tử còn lại em phải tính trung bình cộng của 7 thằng (không tính thằng nhỏ nhất).
- Cứ thế…
Tổng quát với $K$ thì còn $N - K$ gói, bỏ gói nhỏ nhất còn $N - K - 1$ gói để chia trung bình. Trong code anh lưu các trung bình vào vector b (b[0] ứng với $K = 1$), đồng thời giữ Max, cuối cùng in ra mọi vị trí có b[i] == Max (in i + 1 vì $K$ bắt đầu từ 1). Duyệt $i$ tăng dần nên các $K$ tự nhiên được in theo thứ tự tăng dần đúng như đề yêu cầu.
Đây là Solve 1 trong code của anh – cách làm vét cạn có độ phức tạp $O(N^2)$:
#include <bits/stdc++.h>
using namespace std;
// O(N^2)
void solve1(int a[], int n){
vector<long double> b;
long double Max = -1;
for(int i = 1; i <= n - 2; ++i){
int sum = 0;
int Min = a[i + 1];
for(int j = i + 1; j <= n; ++j){
sum += a[j];
Min = min(Min, a[j]);
}
b.push_back((long double)(sum - Min) / (n - i - 1));
Max = max(Max, b.back());
}
for(int i = 0; i < b.size(); ++i){
if(b[i] == Max){
cout << i + 1 << " ";
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n + 1];
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
solve1(a, n);
return 0;
}import sys
def solve1(a, n):
b = []
Max = -1
for i in range(1, n - 1):
total = 0
Min = a[i + 1]
for j in range(i + 1, n + 1):
total += a[j]
Min = min(Min, a[j])
avg = (total - Min) / (n - i - 1)
b.append(avg)
Max = max(Max, avg)
for i in range(len(b)):
if b[i] == Max:
print(i + 1, end=' ')
input = sys.stdin.read
data = list(map(int, input().split()))
n = data[0]
a = [0] + data[1:]
solve1(a, n)Mỗi $K$ phải duyệt lại $N - K$ phần tử ⇒ tổng cỡ $N^2 / 2$ phép tính. Với subtask $n \le 10^2$ thì quá nhẹ, nhưng với $n = 10^5$ là cỡ $5 \cdot 10^9$ phép tính ⇒ TLE (mình đo thử: bản C++ chạy gần 6 giây).
Cách 2Mảng Sum và Min hậu tố – O(N)
Thì em nhìn kỹ vấn đề 1 chút là em sẽ nhìn ra cách với mỗi giá trị $K$ em chỉ cần $O(1)$ để biết được trung bình cộng của các thằng còn lại (không tính thằng nhỏ nhất) là bao nhiêu, nên tính ra bài đó độ phức tạp sẽ chỉ là $O(N)$ em nha. Em để ý phần còn lại luôn là một đoạn cuối mảng (hậu tố) từ vị trí $K + 1$ đến $N$, nên em sẽ có:
- Mảng
Mincó $N$ phần tử với ý nghĩa:Min[i]là phần tử nhỏ nhất tính từ vị trí $i$ đến cuối mảng. - Mảng
Sumcó $N$ phần tử với ý nghĩa:Sum[i]là tổng các phần tử từ vị trí $i$ đến cuối mảng.
Đó, thì tạo ra 2 mảng này chỉ cần $O(N)$ là xong, và khi có 2 mảng này rồi thì em duyệt lần lượt từng giá trị $K$ từ $1$ đến $N - 2$ theo như đề quy ước, với mỗi giá trị $K$ em chỉ cần $O(1)$, tức là ngay lập tức biết được trung bình cộng các phần tử bên phải còn lại không tính thằng nhỏ nhất là bao nhiêu:
Anh nói đến đây là rõ lắm rồi á nha ^^
Làm sao tạo mảng Min trong O(N)?
Một vấn đề mà có thể em gặp khó khăn là làm sao tạo ra mảng Min như anh nói ở trên với độ phức tạp $O(N)$? Thì em duyệt ngược mảng thôi:
Min[n − 1] = min(a[n − 1], Min[n])
Min[n − 2] = min(a[n − 2], Min[n − 1])
…
Cứ thế… em nhìn ra quy tắc chưa? Min[i] = min(a[i], Min[i + 1]). Tại vì ta đã nói Min[i] là phần tử nhỏ nhất từ vị trí $i$ đến cuối mảng, nên tại đó sẽ xét a[i] với Min[i + 1] (tức là phần tử nhỏ nhất từ $i + 1$ đến cuối mảng), thằng nào nhỏ hơn thì chọn nó vào Min[i]. Mảng Sum cũng y chang: Sum[i] = a[i] + Sum[i + 1].
Em nhập dãy rồi bấm Tiếp để xem cách dựng 2 mảng từ cuối lên và tính trung bình cho từng $K$:
Để anh cho em tham khảo code của anh – Solve 2 là cách làm tối ưu có độ phức tạp $O(N)$:
#include <bits/stdc++.h>
using namespace std;
// O(N)
void solve2(int a[], int n){
int Sum[n + 1], Min[n + 1];
Sum[n] = Min[n] = a[n];
for(int i = n - 1; i >= 1; --i){
Sum[i] = a[i] + Sum[i + 1];
Min[i] = min(a[i], Min[i + 1]);
}
vector<long double> b;
long double Max = -1;
for(int i = 1; i <= n - 2; ++i){
b.push_back((long double)(Sum[i + 1] - Min[i + 1]) / (n - i - 1));
Max = max(Max, b.back());
}
for(int i = 0; i < b.size(); ++i){
if(b[i] == Max){
cout << i + 1 << " ";
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n + 1];
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
solve2(a, n);
return 0;
}import sys
def solve2(a, n):
Sum = [0] * (n + 1)
Min = [0] * (n + 1)
Sum[n] = Min[n] = a[n]
for i in range(n - 1, 0, -1):
Sum[i] = a[i] + Sum[i + 1]
Min[i] = min(a[i], Min[i + 1])
b = []
Max = -1
for i in range(1, n - 1):
avg = (Sum[i + 1] - Min[i + 1]) / (n - i - 1)
b.append(avg)
Max = max(Max, avg)
for i in range(len(b)):
if b[i] == Max:
print(i + 1, end=' ')
input = sys.stdin.read
data = list(map(int, input().split()))
n = data[0]
a = [0] + data[1:]
solve2(a, n)- Bước input: $O(N)$.
- Bước tiền xử lý (dựng
Sum,Min): $O(N)$. - Bước xử lý chính (duyệt $K$, mỗi $K$ mất $O(1)$): $O(N)$.
⇒ Tổng là: $O(N)$.
b[i] == Max với số thực long double. Thường so sánh bằng số thực là nguy hiểm, nhưng ở đây mỗi trung bình được tính bằng đúng 1 phép chia của 2 số nguyên chính xác (tử $\le 10^9$ vừa kiểu int), mà phép chia số thực luôn được làm tròn đúng chuẩn IEEE, nên 2 phân số bằng nhau (vd $8/2$ và $12/3$) luôn cho ra cùng 1 giá trị ⇒ so sánh == vẫn đúng. Nếu muốn tuyệt đối an toàn, em có thể so sánh 2 phân số $p_1/q_1$ và $p_2/q_2$ bằng phép nhân chéo số nguyên $p_1 q_2$ với $p_2 q_1$ (dùng long long).solve1, solve2 thành 2 chương trình riêng cho dễ đọc). Cả 4 bản đã được kiểm tra với 300 bộ test ngẫu nhiên ($3 \le n \le 12$, có nhiều số 0, nhiều số trùng nhau để tạo ra nhiều $K$ cùng đạt max) so với code tính trực tiếp bằng phân số chính xác (Fraction): khớp 100%. Với $n = 10^5$, bản C++ Cách 2 chạy khoảng 0.01 giây, bản Python khoảng 0.1 giây; Cách 1 C++ mất gần 6 giây.