Chênh lệch

Nguồn: NTUCoder · Codeforces Group Độ khó: Trung bình Mảng cộng dồn Tìm kiếm nhị phân

Đề bài

Các bài tập về dãy số rất hay và thường xuyên gặp trong các kỳ thi của các NTUcoder. Hôm nay bài tập thử thách cho các bạn là tìm độ chênh lệch như sau:

Cho một dãy số gồm $N$ số nguyên dương $A_1, A_2, \ldots, A_N$. Với một cặp số $(u, v)$ bạn hãy tìm độ chênh lệch bé nhất khi chia đoạn con $[A_u .. A_v]$ thành hai phần.

Bạn hãy xem ví dụ:

Dãy A: 3 1 4 2 5
Với cặp $(2, 5)$ bạn cần tìm chênh lệch nhỏ nhất khi chia đoạn này ra hai phần. Ví dụ có các cách chia sau: (1) và (4, 2, 5); (1, 4) và (2, 5); (1, 4, 2) và (5); (1, 4, 2, 5) và (); Khi đó chênh lệch bé nhất là 2 – tương ứng với cặp (1, 4) (2, 5).

Input

Dòng đầu tiên là hai số nguyên dương $N, Q$ ($1 \le N, Q \le 10^5$). $Q$ là số lượng truy vấn.
Dòng tiếp theo là $N$ số nguyên dương trong dãy A ($A_i \le 10^9$).
$Q$ dòng tiếp theo mỗi dòng là 2 số nguyên dương $(u, v)$. Mỗi cặp số là một truy vấn cần bạn trả lời.

Output

Gồm $Q$ dòng, dòng thứ $i$ là giá trị chênh lệch nhỏ nhất tìm được ứng với truy vấn $i$.

Subtask

50% số test đầu tiên có $N, Q \le 10^4$.
50% số test còn lại không có giới hạn gì thêm.

Ví dụ – input

5 1
3 1 4 2 5
2 5

Ví dụ – output

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 😇.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

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 Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1: Vét cạn$O(Q \times N)$, khoảng 100 giây trong trường hợp xấu nhất ⇒ TLE Cách 2: Cộng dồn + Nhị phân$O(Q \log N)$, chạy chưa tới 0.25 giây ⇒ AC

TLECách 1: vét cạn

Một tư duy đơn giản nhất cho bài này đó là vét cạn xét tất cả mọi trường hợp có thể. Nghĩa là với mỗi đoạn $u$ $v$ trong dãy số sau khi đọc từ input thì ta sẽ đi tính tổng toàn bộ các phần tử trong đoạn $u$ $v$ đó, gọi đó là sum. Rồi thì bắt đầu duyệt xét lần lượt từng vị trí $i$ trong đoạn từ $u$ đến $v$:

sum1 sẽ là tổng các phần tử từ $u$ đến $i$;
sum2 sẽ là tổng các phần tử còn lại, tính được bằng công thức sum2 = sum - sum1;
rồi thì so sánh chênh lệch giữa sum1 và sum2, cập nhật lại vào biến Min.

Quy trình ở trên cứ thế lặp lại khi xét qua vị trí $i$ tiếp theo và cứ thế $i$ sẽ xét từ $u$ đến $v$ xong thì dừng, lúc này in ra kết quả biến Min chính là chênh lệch nhỏ nhất của trường hợp đoạn $u$ $v$ vừa đọc. Ta sẽ tiếp tục đọc đoạn $u$ $v$ tiếp theo và lặp lại toàn bộ quy trình ở trên cho đến khi hết $Q$ truy vấn.

Với ví dụ của đề, truy vấn $(2, 5)$ có sum = 1 + 4 + 2 + 5 = 12, vét cạn sẽ lần lượt xét (dòng xanh là chênh lệch nhỏ nhất):

i	Phần 1: từ u đến i	Phần 2: còn lại	sum1	sum2	\|sum1 − sum2\|
2	(1)	(4, 2, 5)	1	11	10
3	(1, 4)	(2, 5)	5	7	2
4	(1, 4, 2)	(5)	7	5	2
5	(1, 4, 2, 5)	()	12	0	12

Source code để các bạn tham khảo nếu làm theo hướng này:

Xem code cách 1 (vét cạn)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    while(q--){
        int u, v;
        cin >> u >> v;
        long long sum = 0;
        for(int i = u; i <= v; ++i){
            sum += a[i];
        }
        long long sum1 = 0, sum2;
        long long Min = LLONG_MAX;
        for(int i = u; i <= v; ++i){
            sum1 += a[i];
            sum2 = sum - sum1;
            Min = min(Min, abs(sum1 - sum2));
        }
        cout << Min << endl;
    }
    return 0;
}

n, q = map(int, input().split())
a = [0] + list(map(int, input().split()))

for _ in range(q):
    u, v = map(int, input().split())
    total = sum(a[u:v + 1])

    sum1 = 0
    Min = float('inf')

    for i in range(u, v + 1):
        sum1 += a[i]
        sum2 = total - sum1
        Min = min(Min, abs(sum1 - sum2))

    print(Min)

C++▶ Chạy tay từng dòng codeCách 1 (vét cạn): tính tổng đoạn, rồi thử mọi vị trí cắt i từ u đến v – O(Q × N).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int n, q;

8 cin >> n >> q;

9 vector<long long> a(n + 1);

10 for(int i = 1; i <= n; ++i){

11 cin >> a[i];

12 }

13 while(q--){

14 int u, v;

15 cin >> u >> v;

16 long long sum = 0;

17 for(int i = u; i <= v; ++i){

18 sum += a[i];

19 }

20 long long sum1 = 0, sum2;

21 long long Min = LLONG_MAX;

22 for(int i = u; i <= v; ++i){

23 sum1 += a[i];

24 sum2 = sum - sum1;

25 Min = min(Min, abs(sum1 - sum2));

26 }

27 cout << Min << endl;

28 }

29 return 0;

30}

Giải thích một số chỗ trong code ở trên:

2 dòng đầu tiên của hàm main (ios::sync_with_stdio(0); cin.tie(0);) sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé). Kinh nghiệm là trong các bài mà cần nhập xuất nhiều, như trường hợp bài này ta thấy phần input có thể lên đến $3 \times 10^5$ số cần nhập, đây là số lượng lớn thì ta nên để thêm 2 dòng này vào đầu để chương trình chạy nhanh hơn. Tất nhiên nếu các bạn code theo ngôn ngữ C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.
Tuy trong đề bài không nói rõ nhưng thông qua việc mô tả giải thích cho trường hợp ví dụ mà đề bài đưa ra thì ta thấy đoạn $u$ $v$ được tính vị trí bắt đầu từ 1 (tức là $u$, $v$ tối thiểu là 1). Trong khi đó bản chất mảng tính index từ 0 nên ở đây mình cho mảng a có $n + 1$ phần tử để index từ 0 đến $n$, coi như bỏ qua không dùng index 0, chỉ dùng index từ 1 đến $n$ cho thống nhất với quy tắc vị trí tính từ 1 của đoạn $u$ $v$ cho dễ làm bài, tránh những sai sót không đáng có. Coi như bỏ phí 1 ô nhớ (index 0) không làm gì cả thì cũng chẳng vấn đề gì, đổi lại đỡ rắc rối cứ nhớ phải trừ đi 1.
Mình cũng nói luôn sẽ rất dở nếu bạn nào làm theo cách đó là cứ cộng dồn tính giá trị sum1, rồi thì lại làm 1 vòng lặp duyệt từ vị trí $i + 1$ đến $v$ để tính ra giá trị sum2, cứ như thế làm liên tục thì lúc này độ phức tạp còn cao hơn so với cách làm ở trên. Đơn giản là ta cứ đi tính tổng hết tất cả, rồi thì sum1 cứ cộng dồn, với mỗi giá trị của sum1 thì tính ra sum2 bằng cách lấy sum trừ cho sum1 là xong, bởi vì bản chất sum1 + sum2 sẽ bằng sum mà. Mình nói vậy thôi chứ mình nghĩ chắc sẽ không có bạn nào cứ mỗi giá trị sum1 lại phải làm vòng lặp duyệt tính giá trị sum2 đâu nhỉ hihi.

Đánh giá độ phức tạp của cách làm này:

Độ phức tạp không gian (Space Complexity): $O(N)$ của mảng a.
Độ phức tạp thời gian (Time Complexity): $O(N)$ của bước đọc dữ liệu mảng a từ input + $Q$ bộ test, trong đó mỗi bộ test sẽ làm 2 lần lặp từ $U$ đến $V$, tức là cả thảy bước này sẽ có độ phức tạp là $O(Q \times 2 \times (V - U + 1))$. Vậy cả thảy sẽ là: $O(N + Q \times 2 \times (V - U + 1))$. Theo quy tắc nhân Big O thì nhân với hằng số ta có thể bỏ qua, vì thế bước xử lý có thể kết luận độ phức tạp là $O(Q \times (V - U + 1))$. Theo quy tắc cộng Big O khi có nhiều thành phần cộng nhau thì sẽ lấy theo thành phần lớn nhất, vì thế tổng quát sau cùng ta có thể kết luận là $O(\max(N, Q \times (V - U + 1)))$.

Thử tính trường hợp xấu nhất (thông thường là khi toàn bộ dữ liệu đều lớn nhất theo như giới hạn đưa ra) thì lúc này ta có $N = 10^5$, $Q = 10^5$, $U = 1$, $V = 10^5$. Lúc này đây sẽ là: $O(\max(10^5, 10^{10}))$ ⇒ lấy theo $10^{10}$.

Như thế thì chắc chắn sẽ bị TLE nếu làm theo cách này, vì giới hạn của 1 giây chỉ được $10^8$ thôi nên $10^{10}$ thế này là đã vượt quá giới hạn cả 100 lần, tức là trong trường hợp xấu nhất cần phải chạy hết 100 giây mới ra được kết quả. Vậy nên ta sẽ cần tìm một cách khác tốt hơn.

Thực ra ngay từ đầu khi ta nhìn ra cách làm này thì ta cũng có thể nhẩm tính để tính toán ra được độ phức tạp thời gian của nó và thấy rõ là nó sẽ bị chạy quá lâu và không thể nộp bài được. Tuy nhiên mình khuyên nếu các bạn vẫn chưa nghĩ ra cách làm tối ưu đảm bảo chạy thành công (AC) thì việc cài đặt trước một phiên bản theo cách vét cạn thế này là điều cần thiết để chúng ta có thể lấy nó làm công cụ đi kiểm tra tính chính xác cho một cách làm tối ưu hơn mà ta sẽ nghĩ ra tiếp về sau. Để mà khi các bạn code theo cách tối ưu mà nộp bài lên bị báo lỗi sai kết quả (WA) thì ta sẽ nhờ cách vét cạn này để tìm ra trường hợp khiến bị sai cụ thể và ta có đáp án đúng cần thiết của trường hợp đó, từ đó ta có cơ sở dò tìm và sửa lỗi lại. Tin mình đi, đây là cách mà mình áp dụng và vượt qua rất nhiều bài khi bị lỗi WA, mình nhanh chóng tìm ra được lỗi và fix thành công. Các bạn xem bài viết này mình có hướng dẫn cách ứng dụng cách vét cạn làm công cụ kiểm tra tính chính xác tại đây: Hạn chế lỗi Wrong Answer bằng vét cạn.

Tìm hướng đi tốt hơn

Các bạn sẽ thấy cách làm ở trên với mỗi đoạn $U$ $V$ ta cứ phải duyệt hết toàn bộ các phần tử từ vị trí $U$ đến hết vị trí $V$ để tính tổng ⇒ bước này tốn $O(V - U + 1)$, rồi sau đó lại xét lại từ $U$ đến $V$ để tính lần lượt 2 biến sum1, sum2 rồi tìm chênh lệch so sánh với Min ⇒ bước này tốn $O(V - U + 1)$. Nên cả thảy sẽ là $O(2 \times (V - U + 1))$. Và ta có $Q$ bộ test nên cả thảy độ phức tạp mới là $O(Q \times 2 \times (V - U + 1))$. Việc phải xét qua đủ $Q$ bộ test là điều không thể nào tránh được bởi nó là input và chắc chắn ta phải đọc hết toàn bộ input là điều bắt buộc cần thiết. Lúc này ta có thể xem lại có cách nào xử lý với mỗi đoạn $U$ $V$ không cần phải duyệt hết toàn bộ mà vẫn có thể ra được kết quả không?

Và đến đây chắc các bạn cũng dần nhận ra vấn đề: việc duyệt hết toàn bộ đoạn $U$ $V$ chính là tìm kiếm tuyến tính. Và nếu hỏi xem tốt hơn tìm kiếm tuyến tính thì sẽ là gì? Câu trả lời quá rõ ràng đó chính là: Tìm kiếm nhị phân. Và ngay trong bài này ở phần mô tả dạng bài trên trang chủ, nếu các bạn bấm vào phần bài tập rồi gõ tên bài thì các bạn sẽ thấy bài này được phân loại vào dạng "tìm kiếm nhị phân". Quá rõ ràng rồi các bạn hen. Nên cách giải quyết tối ưu cho bài này là ta phải dùng tìm kiếm nhị phân (Binary Search) các bạn nha. Nếu bạn nào chưa biết về kiến thức này thì cần phải tìm hiểu trên Google thêm rồi thì mới đọc tiếp mới hiểu những gì mình viết ở dưới đây nhé, mình sẽ không giải thích lại những khái niệm căn bản của tìm kiếm nhị phân là gì nha vì không đủ thời gian mà mình chỉ ứng dụng vào bài này giải quyết thôi, mong các bạn thông cảm.

Thì vấn đề đặt ra là muốn áp dụng tìm kiếm nhị phân thì chúng ta phải có danh sách các phần tử có thứ tự tăng dần hay giảm dần, nói chung là phải có thứ tự thì mới áp dụng được chứ không thể nào danh sách ngẫu nhiên mà áp dụng tìm kiếm nhị phân được các bạn nha. Vậy giờ phải nhìn lại xem chúng ta cần phải tạo ra nguyên liệu cần thiết như thế nào đây 😛? Từ đó mới dùng công thức (giải thuật) và chế biến ra món ăn thành công (ra đáp án đúng cần thiết) 😊

Kỹ thuật bổ trợ: mảng cộng dồn (Prefix Sum)

Thì tiếp tục phải dùng tới 1 kỹ thuật bổ trợ để tiền xử lý dữ liệu. Kỹ thuật đó có tên là "tổng tiền tố" (tên tiếng Anh là: Prefix Sum) hay còn thường gọi với tên là "mảng cộng dồn". Kỹ thuật này sẽ giúp chúng ta có thể nhanh chóng tính ra tổng giá trị các phần tử trong đoạn từ $U$ đến $V$ và từ đó tạo ra được danh sách có thứ tự để áp dụng tìm kiếm nhị phân trả ra được độ chênh lệch nhỏ nhất.

Kỹ thuật mảng cộng dồn này đơn giản lắm các bạn. Ví dụ đề bài đưa ra ta có danh sách là: 3, 1, 4, 2, 5 hen. Giờ thì nguyên tắc là ta sẽ tạo ra mảng mà phần tử hiện tại là tổng của chính nó với tất cả các phần tử đứng trước nó (vị trí index bé hơn nó). Vậy nên từ mảng 3, 1, 4, 2, 5 ta tạo ra mảng cộng dồn sẽ là:

3 (vì trước phần tử 3 chẳng có phần tử nào cả)
3 + 1 = 4
3 + 1 + 4 = 8
3 + 1 + 4 + 2 = 10
3 + 1 + 4 + 2 + 5 = 15

Vậy ta có mảng cộng dồn là: 3, 4, 8, 10, 15.

Thì ở trên là mình lý giải cho các bạn hiểu phần tử hiện tại là tổng các phần tử đứng trước nó cộng với chính nó, là mô tả các bạn hiểu lý thuyết thôi. Chứ bản chất khi tạo ra mảng cộng dồn ta chỉ cần lấy phần tử hiện tại cộng thêm với phần tử gần nhất trước nó là được, bởi phần tử gần nhất trước đó đã thỏa là tổng các phần tử từ đầu đến chính nó nên ta chỉ cần lấy nó cộng vào thêm thôi. Cụ thể là: 3; 1 + 3 = 4; 4 + 4 = 8; 2 + 8 = 10; 5 + 10 = 15. Và các bạn thấy đó mảng cộng dồn sau cùng vẫn là: 3, 4, 8, 10, 15.

Mảng ban đầu3_[1]1_[2]4_[3]2_[4]5_[5]

Mảng cộng dồn3_[1]4_[2]8_[3]10_[4]15_[5]

Rồi thì giờ giả sử ta cần tính tổng các phần tử trong đoạn từ $U = 2$ đến $V = 4$, tức là: a[2] + a[3] + a[4] (mảng a là mảng ban đầu). Lúc này đây công thức đơn giản là: PrefixSum[V] - PrefixSum[U - 1], tức là trong trường hợp này sẽ là: PrefixSum[4] - PrefixSum[1] = 10 − 3 = 7 (đúng bằng 1 + 4 + 2).

Tại sao lại như vậy? Vì PrefixSum[4] = a[1] + a[2] + a[3] + a[4], PrefixSum[1] = a[1]. Vậy có phải khi trừ nhau thì sẽ triệt tiêu a[1] đi, cuối cùng còn lại: a[2] + a[3] + a[4] không? Chỗ này các bạn cứ kẻ trục số ra sẽ nhìn thấy rõ ngay thôi:

PrefixSum[V] chính là đoạn (1). Rõ ràng giờ ta chỉ cần tìm đoạn từ $U$ đến $V$ thì nó sẽ lấy 2 đoạn trừ nhau, và nhớ là trừ cho PrefixSum[U - 1] (đoạn (2)) nhé, bởi ta đang cần tính tổng từ $U$ đến $V$ mà. Còn chừng nào cần tính tổng từ $U + 1$ đến $V$ lúc đó ta sẽ trừ cho PrefixSum[U].

Đến đây các bạn hiểu rõ rồi hen. Vậy ngay từ bước đọc dữ liệu mảng a từ input ta sẽ lấy chính mảng a biến nó thành mảng cộng dồn luôn, khi mà giá trị a[i] đọc vào sẽ cộng dồn với a[i - 1] trước đó. Sau quá trình đọc mảng a từ input thì lúc này đây mảng a chính là mảng cộng dồn luôn, ta lấy ngay mảng a biến nó thành mảng cộng dồn, không cần tốn bộ nhớ tạo thêm mảng mới làm gì.

Chìa khoá

Mỗi đoạn $U$ $V$ cần tính tổng thì ta chỉ cần gọi: a[v] - a[u - 1] là ra ngay kết quả trong $O(1)$ (độ phức tạp hằng số, tức là ngay lập tức ra kết quả) chứ không cần như cách làm trước đó là phải cần vòng lặp duyệt từ $U$ đến $V$ với độ phức tạp $O(V - U + 1)$.

ACCách 2: tìm kiếm nhị phân trên mảng cộng dồn

Rồi thì các bạn sẽ thấy tính chất của mảng cộng dồn là phần tử sau sẽ được cộng với phần tử trước đó, mà các phần tử của dãy đều là số nguyên dương, nên mảng cộng dồn sẽ có tính chất tăng dần. Và lúc này đây quá hợp lý để ta áp dụng tìm kiếm nhị phân. Cụ thể như sau:

Ta đặt Left = U, Right = V. Điều kiện lặp là khi Left <= Right.
Ta tính ra vị trí Mid = (Left + Right) / 2. Có Mid ta sẽ tính tổng các phần tử từ $U$ đến Mid, gọi tổng đó là Sum1; nhờ mảng cộng dồn hỗ trợ nên cũng trong $O(1)$ ngay lập tức ra được đáp án. Ta tính ra Sum2 là phần còn lại bằng cách lấy Sum - Sum1. Từ đó tính ra chênh lệch giữa 2 phần Sum1, Sum2 rồi so sánh cập nhật lại vào biến Min.
Nếu thấy Sum1 đang nhỏ hơn Sum2 thì ta tăng Left = Mid + 1. Khá dễ để hiểu vì sao lại như vậy đúng không? Bởi Sum1 là tổng các phần tử từ $U$ đến Mid, nếu nó đang nhỏ hơn Sum2 thì ta phải tăng Sum1 lên để cố gắng thu nhỏ lại khoảng cách chênh lệch giữa 2 thằng. Mà muốn tăng Sum1 lên thì phải tăng Mid lên, mà muốn tăng Mid lên thì phải cập nhật lại Left tăng lên để từ đó tính lại Mid là trung bình giữa Left và Right thì lúc này Mid mới tăng lên. Thế nên mới là: Left = Mid + 1.
Tương tự ngược lại nếu Sum2 nhỏ hơn Sum1 thì giảm Right = Mid - 1.
Còn nếu tại thời điểm nào mà Sum1, Sum2 bằng nhau thì ta break luôn, bởi lúc này chênh lệch giữa tụi nó là 0 và đây là chênh lệch nhỏ nhất có thể rồi, không có cái nào nhỏ hơn nữa. Nếu may mắn gặp trường hợp này để kết thúc sớm thì quá khỏe, còn nếu không thì cứ liên tục cập nhật lại Left Right cho đến khi Left > Right thì vòng lặp sẽ dừng lại.
Lúc này ta đi in ra biến Min là kết quả chênh lệch nhỏ nhất trong tất cả những trường hợp đã xét đến. Rồi thì xét qua đoạn $U$ $V$ mới và lặp lại toàn bộ quy trình ở trên.

Lưu ý chỗ này dễ bị nhầm lẫn: ta cần tính tổng từ $U$ nha, chứ không phải từ Left. Nếu tính từ Left là không đúng, bởi vì Left liên tục bị thay đổi trong quá trình tìm kiếm nhị phân, nên ta phải tính từ $U$ nhé: Sum1 = a[Mid] - a[U - 1].

Em nhập dãy số và đoạn $u$ $v$ rồi bấm Tiếp để xem tìm kiếm nhị phân dời điểm cắt mid (vạch đỏ) như thế nào cho tới khi hai phần cân nhất:

Dãy A u v

Ví dụ nhanh:

Chạy thử với truy vấn $(2, 5)$ của ví dụ, mảng cộng dồn a = 3, 4, 8, 10, 15 và Sum = a[5] - a[1] = 15 − 3 = 12:

Bước	Left	Right	Mid	sum1	sum2	Min	Cập nhật
1	2	5	3	a[3] − a[1] = 5	12 − 5 = 7	2	sum1 < sum2 ⇒ Left = 4
2	4	5	4	a[4] − a[1] = 7	12 − 7 = 5	2	sum1 > sum2 ⇒ Right = 3

Đến đây Left = 4 > Right = 3 nên vòng lặp dừng, in ra Min = 2, đúng với đáp án đề cho. Chỉ 2 bước thay vì phải xét hết 4 cách chia như vét cạn.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 1);
    a[0] = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        a[i] += a[i - 1];
    }
    while(q--){
        int l, r;
        cin >> l >> r;
        int u = l, v = r;
        long long sum = a[r] - a[l - 1];
        long long Min = LLONG_MAX;
        while(l <= r){
            int mid = (l + r) / 2;
            long long sum1 = a[mid] - a[u - 1];
            long long sum2 = sum - sum1;
            Min = min(Min, abs(sum1 - sum2));
            if(sum2 > sum1){
                l = mid + 1;
            }
            else if(sum2 < sum1){
                r = mid - 1;
            }
            else{
                break;
            }
        }
        cout << Min << endl;
    }
    return 0;
}

n, q = map(int, input().split())
a = [0] + list(map(int, input().split()))

for i in range(1, n + 1):
    a[i] += a[i - 1]

for _ in range(q):
    l, r = map(int, input().split())
    u, v = l, r
    total = a[r] - a[l - 1]
    Min = float('inf')

    while l <= r:
        mid = (l + r) // 2
        sum1 = a[mid] - a[u - 1]
        sum2 = total - sum1
        Min = min(Min, abs(sum1 - sum2))

        if sum2 > sum1:
            l = mid + 1
        elif sum2 < sum1:
            r = mid - 1
        else:
            break

    print(Min)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    a = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = a[i - 1] + int(data[i + 1])

    out = []
    pos = n + 2
    for _ in range(q):
        l, r = int(data[pos]), int(data[pos + 1])
        pos += 2
        base = a[l - 1]
        total = a[r] - base
        Min = total

        while l <= r:
            mid = (l + r) // 2
            sum1 = a[mid] - base
            diff = 2 * sum1 - total      # = sum1 - sum2
            if diff < 0:
                if -diff < Min: Min = -diff
                l = mid + 1
            elif diff > 0:
                if diff < Min: Min = diff
                r = mid - 1
            else:
                Min = 0
                break

        out.append(Min)

    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

C++▶ Chạy tay từng dòng codeCách 2: mảng cộng dồn + tìm kiếm nhị phân điểm cắt – O(Q log N).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int main() {

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int n, q;

8 cin >> n >> q;

9 vector<long long> a(n + 1);

10 a[0] = 0;

11 for(int i = 1; i <= n; ++i){

12 cin >> a[i];

13 a[i] += a[i - 1];

14 }

15 while(q--){

16 int l, r;

17 cin >> l >> r;

18 int u = l, v = r;

19 long long sum = a[r] - a[l - 1];

20 long long Min = LLONG_MAX;

21 while(l <= r){

22 int mid = (l + r) / 2;

23 long long sum1 = a[mid] - a[u - 1];

24 long long sum2 = sum - sum1;

25 Min = min(Min, abs(sum1 - sum2));

26 if(sum2 > sum1){

27 l = mid + 1;

28 }

29 else if(sum2 < sum1){

30 r = mid - 1;

31 }

32 else{

33 break;

34 }

35 }

36 cout << Min << endl;

37 }

38 return 0;

39}

Toàn bộ những gì mà code mình cài đặt đều hoàn toàn dựa theo đúng những gì mình đã phân tích ở trước đó. Nên nếu bạn nào xem code mà không hiểu chỗ nào thì các bạn có thể đọc kỹ lại những gì mình phân tích giải thích ở trước đó nha.

Về code Python: bản "Python" chuyển y nguyên từ C++ dùng input() và print() cho từng truy vấn, với $Q = 10^5$ truy vấn thì nhập xuất từng dòng như vậy khá chậm và có thể bị TLE do bài để chung giới hạn 1 giây cho cả Python. Bản "Python (nhập xuất nhanh)" vẫn đúng ý tưởng y như trên, chỉ khác là đọc toàn bộ input một lần bằng sys.stdin.buffer.read(), gom kết quả lại rồi in ra một lần, chạy nhanh hơn khoảng 3 lần. Bạn nào code Python thì nên nộp bản này nhé.

Đánh giá độ phức tạp của cách làm này:

Độ phức tạp không gian (Space Complexity): $O(N)$ của mảng a.
Độ phức tạp thời gian (Time Complexity): $O(N)$ của bước đọc mảng a từ input + vòng lặp qua $Q$ bộ test, với mỗi bộ test tìm kiếm nhị phân trên đoạn từ $U$ đến $V$ tức là tốn độ phức tạp là $O(\log(V - U + 1))$. Vậy cả thảy bước xử lý sẽ có độ phức tạp: $O(Q \times \log(V - U + 1))$. Theo quy tắc cộng Big O khi có nhiều thành phần cộng nhau sẽ lấy theo thành phần lớn nhất nên ta có thể kết luận là $O(\max(N, Q \times \log(V - U + 1)))$.

Thử tính trường hợp xấu nhất thì lúc này ta có $N = 10^5$, $Q = 10^5$, $U = 1$, $V = 10^5$. Lúc này đây sẽ là: $O(\max(10^5, 10^5 \times \log(10^5)))$. Thì $10^5 \times \log(10^5)$ chắc chắn là lớn hơn $10^5$ rồi nên ta chỉ cần tính theo nó. Cũng nói rõ $\log$ ở đây là logarit cơ số 2 các bạn nha, thường trong độ phức tạp dù là cơ số mấy ta cũng chỉ cần ký hiệu là $\log$ thôi là được, nhưng nói rõ tìm kiếm nhị phân thì là $\log_2$ nhé (đã gọi là "nhị" tức là 2 mà 😋). Vậy $\log_2(10^5) \approx 17$, cả thảy là: $17 \times 10^5$. Thế này thì ít hơn $10^8$ nên chắc chắn sẽ chạy trong giới hạn 1 giây. Cụ thể khi mình nộp code lên thì theo trang web đưa ra test lâu nhất là chạy trong 250 ms nha các bạn, nhanh gấp 4 lần so với ngưỡng giới hạn 1 giây.

Cách 1: Vét cạn

$O(Q \times N) \approx 10^{10}$ phép tính

≈ 100 giây ⇒ TLE

Cách 2: Cộng dồn + Tìm kiếm nhị phân

$O(Q \log N) \approx 17 \times 10^5$ phép tính

≈ 0.25 giây ⇒ AC

Đến đây các bạn đã thấy cái hay của giải thuật chưa? Cách làm trước đó trong trường hợp xấu nhất phải chạy đến cả 100 giây (hơn 1 phút rưỡi) trong khi cách làm này chỉ cần 0.25 giây là ra ngay kết quả, tức là chớp mắt cái là ra kết quả ngay ahihi ☺️

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán

Chênh lệch

Đề bài

Lời mở đầu

TLECách 1: vét cạn

Tìm hướng đi tốt hơn

Kỹ thuật bổ trợ: mảng cộng dồn (Prefix Sum)

ACCách 2: tìm kiếm nhị phân trên mảng cộng dồn

Nhận xét

Đăng nhận xét

Khóa học Lập trình Thuật toán thi đấu

Lộ trình học thuật toán từ A đến Z

Thành tích học viên