Chia Mảng (CSES Array Division)
Đề bài
Bạn được cho một mảng chứa $n$ số nguyên dương. Nhiệm vụ của bạn là chia mảng thành $k$ đoạn con sao cho tổng lớn nhất trong các đoạn con nhỏ nhất có thể.
Input
- Dòng đầu vào đầu tiên chứa hai số nguyên $n$ và $k$: kích thước của mảng và số lượng đoạn con trong cách chia.
- Dòng tiếp theo chứa $n$ số nguyên $x_1, x_2, \ldots, x_n$: nội dung của mảng.
Output: in một số nguyên: tổng lớn nhất của một đoạn con trong cách chia tối ưu.
Constraints: $1 \le n \le 2 \cdot 10^5$, $1 \le k \le n$, $1 \le x_i \le 10^9$.
Note: một cách chia tối ưu của ví dụ là $[2, 4], [7], [3, 5]$, trong đó tổng của các đoạn con là $6, 7, 8$. Tổng lớn nhất là tổng cuối cùng $8$.
5 3
2 4 7 3 585 2
1 5 2 2 375 3
1 5 2 2 36Hai test thêm là anh đưa ra để em hiểu rõ hơn: test 1 chia thành $[1, 5]$ và $[2, 2, 3]$, nhóm $[2, 2, 3]$ có tổng lớn nhất là 7; test 2 chia thành $[1, 5]$, $[2, 2]$ và $[3]$, nhóm $[1, 5]$ có tổng lớn nhất là 6.
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 toàn bộ 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 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 LQDOJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Đọc kỹ đề bài, đặc biệt là xem phần ví dụ, thì chắc em đã nhận ra khái niệm "đoạn con" mà đề bài nói chính là "đoạn con liên tiếp" nhé.
Kiến thứcChặt nhị phân đáp án là gì?
Bài này dùng kỹ thuật tìm kiếm nhị phân trên đáp án, tiếng Anh là Binary search the answer, dân trong ngành còn gọi là chặt nhị phân đáp án.
Giả sử em đã biết miền đáp án nằm trong một đoạn từ Left đến Right. Thay vì cứ thử lần lượt từ Left đến Right sẽ rất lâu, em thử giả định nó nằm ở giữa, sau đó kiểm tra: nếu xác định đáp án nằm ở nửa bên phải thì tìm tiếp nửa bên phải, nằm ở nửa bên trái thì tìm tiếp nửa bên trái. Lặp lại quy trình cho đến khi tìm được hoặc không tìm được.
Cũng giống như em đọc sách: cần tìm một trang nào đó thì thay vì lật từ đầu đến cuối, em lật ở giữa, dựa vào số trang để biết trang cần tìm nằm ở nửa bên phải hay nửa bên trái, rồi lại tìm tiếp như vậy 📖.
Ý tưởngÁp dụng vào bài này
Với test 1: dãy 1 5 2 2 3 và $K = 2$.
- Nếu chỉ chia $K = 1$ đoạn thì tổng lớn nhất là cả dãy: $1 + 5 + 2 + 2 + 3 = 13$. Đây là đáp án lớn nhất có thể.
- Nếu chia $K = N$ đoạn (mỗi phần tử một đoạn) thì tổng lớn nhất là phần tử lớn nhất $= 5$. Đây là đáp án nhỏ nhất có thể.
Vậy xác định $L = 5$, $R = 13$, đáp án nằm trong đoạn này.
• Cần ≤ K đoạn → $X$ thoả mãn (ít hơn $K$ cũng được, vì muốn đủ đúng $K$ đoạn thì cắt thêm vài chỗ, tổng các đoạn chỉ nhỏ đi).
• Cần > K đoạn → $X$ quá nhỏ, không được.
Thử $M = (L + R) / 2 = 18 / 2 = 9$. Với dãy 1 5 2 2 3 chia được $[1, 5, 2]$ và $[2, 3]$: đoạn đầu dừng ở 1 5 2, vì lấy thêm 2 nữa thì tổng thành 10 > 9. Được 2 đoạn ≤ K nên 9 thoả mãn. Nhưng ta cần đáp án nhỏ nhất nên chưa vội lấy 9, tìm tiếp sang trái: $R = M - 1 = 8$.
$L = 5$, $R = 8$ → $M = 6$: chia ra $[1, 5], [2, 2], [3]$, cần tới 3 đoạn > K = 2, không được. Phải tìm lên: $L = M + 1 = 7$.
$L = 7$, $R = 8$ → $M = 7$: chia ra $[1, 5], [2, 2, 3]$, được 2 đoạn, lấy được. Thử nhỏ hơn: $R = 6$, lúc này $L > R$ nên dừng. Đáp án là 7.
Tổng quát chi phí là $O(N \cdot \log(\text{sum} - \max a_i))$.
Chạy tayChạy tay với dãy 2 7 4 5 10 9 8, K = 3
Sau đó em ấy nhờ mình chạy tay quy trình với test 2 7 4 5 10 9 8, $K = 3$. Ta có $sum = 45$, $Max = 10$, nên $left = 10$, $right = 45$:
| [L, R] | mid | Chia tham lam (tổng mỗi đoạn ≤ mid) | Số đoạn | So với K = 3 |
|---|---|---|---|---|
| [10, 45] | 27 | [2, 7, 4, 5] | [10, 9, 8] | 2 | ✔ nhận, R = 26 |
| [10, 26] | 18 | [2, 7, 4, 5] | [10] | [9, 8] | 3 | ✔ nhận, R = 17 |
| [10, 17] | 13 | [2, 7, 4] | [5] | [10] | [9] | [8] | 5 | ✘ loại, L = 14 |
| [14, 17] | 15 | [2, 7, 4] | [5, 10] | [9] | [8] | 4 | ✘ loại, L = 16 |
| [16, 17] | 16 | [2, 7, 4] | [5, 10] | [9] | [8] | 4 | ✘ loại, L = 17 |
| [17, 17] | 17 | [2, 7, 4] | [5, 10] | [9, 8] | 3 | ✔ nhận, R = 16 |
| Đáp án (in ra L) | 17 | |||
Khi $left > right$ thì dừng, in ra $left$ là kết quả, đáp án là 17: chia được $[2, 7, 4]$, $[5, 10]$, $[9, 8]$, tổng lần lượt 13, 15, 17.
Minh hoạTự chạy từng bước
Em nhập dãy và $K$ (tối đa 14 phần tử) rồi bấm Tiếp. Mỗi màu là một đoạn trong cách chia tham lam với giá trị mid đang thử:
CodeSource code
Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<long long> a(n + 1);
long long sum = 0;
long long Max = LLONG_MIN;
for(int i = 1; i <= n; ++i){
cin >> a[i];
sum += a[i];
Max = max(Max, a[i]);
}
if(m == 1){
cout << sum;
return 0;
}
if(m == n){
cout << Max;
return 0;
}
long long left = Max, right = sum;
while(left <= right){
long long mid = (left + right) / 2;
int k = 1;
long long s = 0;
for(int i = 1; i <= n; ++i){
if(s + a[i] <= mid){
s += a[i];
}
else{
s = a[i];
k++;
}
}
if(k <= m){
right = mid - 1;
}
else{
left = mid + 1;
}
}
cout << left;
return 0;
}import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
total_sum = sum(a[1:])
Max = max(a[1:])
if m == 1:
print(total_sum)
elif m == n:
print(Max)
else:
left = Max
right = total_sum
while left <= right:
mid = (left + right) // 2
k = 1
s = 0
for i in range(1, n + 1):
if s + a[i] <= mid:
s += a[i]
else:
s = a[i]
k += 1
if k <= m:
right = mid - 1
else:
left = mid + 1
print(left)Hai trường hợp đặc biệt được xử lý trước cho nhanh: $K = 1$ thì đáp án là tổng cả dãy, $K = N$ thì đáp án là phần tử lớn nhất. Chú ý dùng long long vì tổng có thể tới $2 \cdot 10^5 \times 10^9 = 2 \cdot 10^{14}$, vượt kiểu int.
Mình đã kiểm tra cả 2 bản code với 400 bộ test ngẫu nhiên so với cách vét cạn mọi cách chia, đều cho cùng kết quả. Với $n = 2 \cdot 10^5$, bản C++ chạy khoảng 0.02 giây; bản Python khoảng 1.3 giây trên máy mình, có thể sát giới hạn thời gian nên các bạn nộp bằng C++ cho chắc nhé.
Nhận xét
Đăng nhận xét