Bài 16.5: Bài tập thực hành sắp xếp trong C++

Chào mừng trở lại với series blog về C++! Hôm nay, chúng ta sẽ cùng nhau đi sâu vào một chủ đề cực kỳ quan trọng và xuất hiện hầu như trong mọi ứng dụng phần mềm: sắp xếp dữ liệu. Dù bạn đang xử lý danh sách các số nguyên, chuỗi ký tự, hay các đối tượng phức tạp hơn, việc sắp xếp giúp dữ liệu của bạn trở nên có tổ chức, dễ dàng tìm kiếm, phân tích và xử lý hiệu quả hơn rất nhiều.

Trong C++, chúng ta có những công cụ mạnh mẽ và tối ưu để thực hiện công việc này. Bài viết này sẽ hướng dẫn bạn cách sử dụng chúng và cung cấp các ví dụ minh họa chi tiết.

1. Sức Mạnh Của Thư Viện Chuẩn C++: `sort` và Các Biến Thể

Trong hầu hết các trường hợp thực tế, cách hiệu quả nhất và được khuyến nghị để sắp xếp trong C++ là sử dụng các hàm có sẵn trong Thư viện Chuẩn C++ (STL), cụ thể là họ hàng của hàm sort. Những hàm này thường triển khai các thuật toán sắp xếp rất hiệu quả (như Introsort - sự kết hợp của QuickSort, HeapSort và InsertionSort) với độ phức tạp trung bình là O(N log N), nơi N là số lượng phần tử.

sort hoạt động trên một phạm vi (range) được định nghĩa bởi hai iterator: iterator đến phần tử đầu tiên và iterator đến sau phần tử cuối cùng.

1.1. `sort`: Sắp xếp cơ bản

Ví dụ đơn giản nhất là sắp xếp một vector các số nguyên theo thứ tự tăng dần.

#include <iostream>
#include <vector>
#include <algorithm> // Cần include <algorithm> để sử dụng sort

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 4};

    cout << "Vector truoc khi sap xep: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // Sap xep vector theo thu tu tang dan
    sort(numbers.begin(), numbers.end());

    cout << "Vector sau khi sap xep (tang dan): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta khai báo và khởi tạo một vector tên là numbers.
Hàm sort được gọi với hai đối số: numbers.begin() trả về iterator đến phần tử đầu tiên và numbers.end() trả về iterator đến vị trí sau phần tử cuối cùng. Đây là cách phổ biến để xác định một phạm vi trong STL.
Mặc định, đối với các kiểu dữ liệu cơ bản như int, sort sẽ sử dụng toán tử < để so sánh và sắp xếp theo thứ tự tăng dần.

1.2. `sort` với Comparator: Tùy chỉnh thứ tự

Nếu bạn muốn sắp xếp theo một tiêu chí khác (ví dụ: giảm dần, theo một trường dữ liệu cụ thể của đối tượng), bạn có thể cung cấp thêm một đối số thứ ba cho sort. Đối số này là một comparator (một hàm hoặc đối tượng hàm - function object) mà sort sẽ sử dụng để xác định thứ tự. Comparator này nhận hai phần tử cùng kiểu và trả về true nếu phần tử đầu tiên nên đứng trước phần tử thứ hai.

1.2.1. Sắp xếp giảm dần

STL cung cấp sẵn các function object như greater<T> để sắp xếp theo thứ tự giảm dần.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // Cần include <functional> cho greater

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 4};

    cout << "Vector truoc khi sap xep: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // Sap xep vector theo thu tu giam dan
    sort(numbers.begin(), numbers.end(), greater<int>());

    cout << "Vector sau khi sap xep (giam dan): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta thêm greater<int>() làm đối số thứ ba. Đây là một đối tượng hàm (function object) cung cấp phép so sánh "lớn hơn".
greater<int>()(a, b) trả về true nếu a > b. sort sử dụng điều này để đặt các phần tử lớn hơn lên trước, dẫn đến kết quả sắp xếp giảm dần.

1.2.2. Sắp xếp các đối tượng tùy chỉnh bằng Lambda Function

Sức mạnh thực sự của sort là khả năng sắp xếp bất kỳ loại dữ liệu nào, miễn là bạn cung cấp cách so sánh chúng. Chúng ta thường sử dụng lambda function làm comparator vì tính ngắn gọn và linh hoạt của nó.

Giả sử chúng ta có struct Person và muốn sắp xếp một danh sách Person dựa trên tuổi của họ.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
        {"David", 25} // Them mot nguoi cung tuoi de test stable_sort sau
    };

    cout << "Danh sach truoc khi sap xep:" << endl;
    for (const auto& p : people) {
        cout << p.name << " (" << p.age << ") ";
    }
    cout << endl;

    // Sap xep theo tuoi tang dan su dung lambda
    sort(people.begin(), people.end(),
              [](const Person& a, const Person& b) {
                  return a.age < b.age; // Tra ve true neu 'a' nen dung truoc 'b'
              });

    cout << "Danh sach sau khi sap xep (theo tuoi tang dan):" << endl;
    for (const auto& p : people) {
        cout << p.name << " (" << p.age << ") ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Chúng ta định nghĩa struct Person với hai thành viên: name (chuỗi) và age (số nguyên).
Comparator là một lambda function: [](const Person& a, const Person& b) { return a.age < b.age; }.
- []: Khung chứa (capture clause) trống, nghĩa là lambda không capture biến nào từ môi trường xung quanh.
- (const Person& a, const Person& b): Danh sách tham số, nhận hai đối tượng Person làm tham chiếu hằng.
- { return a.age < b.age; }: Phần thân của lambda. Nó so sánh tuổi của a và b. Nếu a.age nhỏ hơn b.age, nó trả về true, báo cho sort biết rằng a nên đứng trước b. Điều này dẫn đến việc sắp xếp theo tuổi tăng dần.

1.3. `stable_sort`: Sắp xếp ổn định

Đôi khi, khi sắp xếp các đối tượng, có những trường hợp hai đối tượng được coi là "bằng nhau" theo tiêu chí sắp xếp (ví dụ: cùng tuổi). stable_sort là một hàm sắp xếp ổn định. Điều này có nghĩa là nếu hai phần tử được coi là bằng nhau theo comparator, thì thứ tự tương đối của chúng trong danh sách đã sắp xếp sẽ giống hệt thứ tự của chúng trong danh sách ban đầu. sort không đảm bảo điều này. Tính ổn định này rất quan trọng trong một số ứng dụng, đặc biệt khi bạn sắp xếp dữ liệu nhiều lần theo các tiêu chí khác nhau.

Quay lại ví dụ Person. Bob và David đều 25 tuổi. Trong danh sách ban đầu, Bob xuất hiện trước David. Nếu chúng ta sử dụng sort, thứ tự của họ trong kết quả sắp xếp là không xác định (có thể Bob trước David hoặc ngược lại). Nếu sử dụng stable_sort, Bob sẽ luôn đứng trước David trong danh sách đã sắp xếp.

#include <iostream>
#include <vector>
#include <algorithm> // Can cho stable_sort
#include <string>

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25}, // Bob xuat hien truoc David trong danh sach goc
        {"Charlie", 35},
        {"David", 25} // David xuat hien sau Bob trong danh sach goc
    };

    cout << "Danh sach truoc khi sap xep:" << endl;
    for (const auto& p : people) {
        cout << p.name << " (" << p.age << ") ";
    }
    cout << endl;

    // Sap xep on dinh theo tuoi tang dan su dung stable_sort
    stable_sort(people.begin(), people.end(),
                     [](const Person& a, const Person& b) {
                         return a.age < b.age;
                     });

    cout << "Danh sach sau khi sap xep (on dinh theo tuoi tang dan):" << endl;
    for (const auto& p : people) {
        cout << p.name << " (" << p.age << ") ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Code này giống hệt ví dụ trước, chỉ thay sort bằng stable_sort.
Kết quả sẽ cho thấy Bob đứng trước David vì đó là thứ tự của họ trong vector ban đầu, mặc dù cả hai đều có cùng tuổi 25. sort không đảm bảo điều này.
stable_sort có thể chậm hơn sort một chút hoặc cần thêm bộ nhớ phụ, nhưng bù lại nó cung cấp tính ổn định cần thiết.

1.4. `partial_sort`: Sắp xếp một phần

Nếu bạn chỉ cần K phần tử nhỏ nhất (hoặc lớn nhất) của danh sách ở đầu danh sách và không quan tâm đến thứ tự của các phần tử còn lại, partial_sort là lựa chọn tối ưu. Nó sắp xếp K phần tử đầu tiên của phạm vi theo đúng thứ tự mà chúng sẽ có nếu toàn bộ phạm vi được sắp xếp.

Ví dụ, bạn muốn tìm 3 số nhỏ nhất trong một vector.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    vector<int> numbers = {10, 4, 7, 1, 9, 3, 6, 2, 8, 5};
    int k = 3; // Muon tim 3 so nho nhat

    cout << "Vector truoc khi partial sort: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // Partial sort de lay 3 phan tu nho nhat
    // Sap xep pham vi [begin(), begin() + k)
    partial_sort(numbers.begin(), numbers.begin() + k, numbers.end());

    cout << "Vector sau khi partial sort (3 phan tu nho nhat o dau): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // 3 phan tu dau tien (numbers[0] den numbers[k-1]) la 3 so nho nhat va da duoc sap xep
    cout << "3 so nho nhat la: ";
    for (int i = 0; i < k; ++i) {
        cout << numbers[i] << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

partial_sort nhận ba iterator: first, middle, và last.
Nó đảm bảo rằng tất cả các phần tử trong phạm vi [first, middle) (tức là từ first đến trước middle) là các phần tử nhỏ nhất trong toàn bộ phạm vi [first, last) và chúng được sắp xếp theo đúng thứ tự.
Các phần tử trong phạm vi [middle, last) không được đảm bảo thứ tự cụ thể nào.
Ở đây, first là numbers.begin(), middle là numbers.begin() + k, và last là numbers.end(). Sau khi gọi hàm, numbers[0] đến numbers[k-1] sẽ chứa K phần tử nhỏ nhất của vector gốc, và chúng đã được sắp xếp tăng dần.

2. Tự Implement Thuật Toán Sắp Xếp Đơn Giản (Chỉ để Học tập)

Mặc dù sort và các hàm liên quan từ STL là lựa chọn hàng đầu cho hiệu suất và tính đúng đắn, việc hiểu và tự tay implement các thuật toán sắp xếp cơ bản như Bubble Sort, Selection Sort, hay Insertion Sort là rất hữu ích để củng cố kiến thức về cấu trúc dữ liệu và giải thuật. Tuy nhiên, hãy luôn nhớ rằng các thuật toán đơn giản này thường có độ phức tạp O(N^2) (kém hiệu quả với dữ liệu lớn) và không nên sử dụng trong các ứng dụng thực tế khi hiệu suất là quan trọng, thay vào đó hãy dùng STL.

Chúng ta hãy thử với Bubble Sort - thuật toán đơn giản nhất để minh họa cách một thuật toán sắp xếp hoạt động ở mức cơ bản.

2.1. Bubble Sort

Bubble Sort hoạt động bằng cách lặp đi lặp lại việc duyệt qua danh sách, so sánh các cặp phần tử liền kề và hoán đổi chúng nếu chúng sai thứ tự. Quá trình này lặp lại cho đến khi không còn cặp nào cần hoán đổi nữa (nghĩa là danh sách đã sắp xếp).

#include <iostream>
#include <vector>
#include <algorithm> // Cần cho swap

// Ham Bubble Sort
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped; // Bien co de kiem tra xem co hoan doi nao xay ra khong

    // Lap qua tat ca cac phan tu cua mang
    for (int i = 0; i < n - 1; ++i) {
        swapped = false; // Moi luot duyet moi bat dau, coi nhu chua hoan doi
        // Duyet tu dau den phan tu thu n-i-1
        // Cac phan tu tu i tro ve cuoi da dung vi tri cua chung
        for (int j = 0; j < n - i - 1; ++j) {
            // Neu phan tu hien tai lon hon phan tu tiep theo, hoan doi chung
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true; // Danh dau la da co hoan doi
            }
        }
        // Neu khong co hoan doi nao trong luot duyet nay, mang da sap xep hoan toan
        if (!swapped) {
            break;
        }
    }
}

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 4};

    cout << "Vector truoc khi sap xep (Bubble Sort): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // Goi ham bubble sort
    bubbleSort(numbers);

    cout << "Vector sau khi sap xep (Bubble Sort): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích:

Hàm bubbleSort nhận một vector arr theo tham chiếu để có thể trực tiếp thay đổi nội dung của nó.
Vòng lặp ngoài (i) chạy n-1 lần. Sau mỗi lần lặp hoàn thành của vòng ngoài, phần tử lớn nhất còn lại trong phạm vi chưa sắp xếp sẽ "nổi bọt" lên vị trí đúng cuối cùng của phạm vi đó.
Vòng lặp trong (j) thực hiện việc so sánh và hoán đổi các cặp phần tử liền kề. Phạm vi của j giảm dần sau mỗi vòng ngoài (n - i - 1) vì các phần tử ở cuối mảng đã được đưa về đúng vị trí của chúng.
Biến swapped là một tối ưu hóa nhỏ: nếu trong một lần duyệt đầy đủ của vòng lặp trong mà không có bất kỳ cặp nào được hoán đổi, điều đó có nghĩa là mảng đã hoàn toàn được sắp xếp và chúng ta có thể thoát khỏi các vòng lặp sớm.
swap từ header <algorithm> là một cách an toàn và hiệu quả để hoán đổi giá trị của hai biến.

3. Tóm tắt: Khi nào sử dụng gì?

sort: Đây là lựa chọn mặc định, hiệu quả nhất và phổ biến nhất cho hầu hết các nhu cầu sắp xếp thông thường. Sử dụng comparator (lambda function, greater, v.v.) để tùy chỉnh thứ tự sắp xếp.
stable_sort: Sử dụng khi bạn cần bảo toàn thứ tự tương đối của các phần tử được coi là bằng nhau theo tiêu chí sắp xếp. Mặc dù có thể kém hiệu quả hơn sort một chút, tính ổn định của nó rất quan trọng trong một số tình huống.
partial_sort: Sử dụng khi bạn chỉ cần tìm và sắp xếp K phần tử nhỏ nhất (hoặc lớn nhất) và đặt chúng ở đầu danh sách, mà không cần sắp xếp toàn bộ danh sách.
Tự implement thuật toán cơ bản (như Bubble Sort): Chỉ nên làm để học tập, củng cố kiến thức về giải thuật và hiểu cách sắp xếp hoạt động ở mức độ thấp. Tránh sử dụng trong code sản phẩm hoặc các ứng dụng thực tế khi hiệu suất là yếu tố quan trọng.

Bài tập ví dụ: C++ Bài 9.B5: Trừ tối thiểu

An có một mảng \(a\) gồm \(n\) số nguyên. Nếu mảng \(a\) có độ dài lớn hơn 1 thì An có thể áp dụng thao tác gọi là trừ tối thiểu cho nó như sau:

Đầu tiên, An tìm số \(m\) nhỏ nhất trong mảng. Nếu có nhiều số nhỏ nhất thì An có thể chọn bất kỳ số nào trong chúng;
Sau đó, phần tử nhỏ nhất đã chọn sẽ bị xóa khỏi mảng. Tiếp theo, mỗi phần tử còn lại của mảng được trừ đi \(m\).

Như vậy sau mỗi thao tác, độ dài của mảng giảm đi \(1\).

Ví dụ nếu \(a = [1, 6, -4, -2, -4]\) thì phần tử nhỏ nhất trong đó là \(a_3 = -4\) và sau thao tác này, mảng sẽ trở thành \(a = [1-(-4), 6-(-4), -2-(-4), -4-(-4)] = [5, 10, 2, 0]\)

Vì An thích những số lớn, nên anh ấy muốn các số trong mảng \(a\) càng lớn càng tốt. Cụ thể, anh ta muốn làm cho số nhỏ nhất trong mảng \(a\) là lớn nhất. Để thực hiện điều này, An có thể áp dụng thao tác trừ tối thiểu cho mảng nhiều lần tùy thích (có thể không thao tác lần nào). Lưu ý rằng thao tác này không thể áp dụng cho mảng có độ dài \(1\).

Hãy giúp An tìm giá trị lớn nhất của phần tử nhỏ nhất của mảng sau khi áp dụng một số (có thể bằng \(0\)) thao tác trừ tối thiểu cho mảng.

INPUT FORMAT

Dòng đầu tiên chứa một số nguyên \(t\ (1\leq t\leq 10^3)\) là số lượng test.

Dòng thứ nhất của mỗi test chứa số nguyên \(n\ (1\leq 10^3)\) là độ dài ban đầu của mảng \(a\);

Dòng thứ hai của mỗi test chứa \(n\) số nguyên \(a_1, a_2,...,a_n\ (-10^9 \le a_i \le 10^9)\) là các phần tử của mảng \(a\)

Dữ liệu vào đảm bảo rằng tổng độ dài các mảng trên tất cả các test không vượt quá \(10^3\).

OUTPUT FORMAT

In ra một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input

Output

Giải thích ví dụ mẫu

Ví dụ 1:
- Dữ liệu: a = [1, 6, -4, -2, -4]
- Giải thích: Sau khi thực hiện thao tác trừ tối thiểu, số nhỏ nhất trong mảng có thể đạt giá trị tối đa là 5.
Ví dụ 2:
- Dữ liệu: a = [-1, 2, 0]
- Giải thích: Sau khi thực hiện thao tác trừ tối thiểu, số nhỏ nhất trong mảng có thể đạt giá trị tối đa là 2.

<br>

1. Hiểu rõ thao tác "Trừ tối thiểu":

Tìm số nhỏ nhất m trong mảng.
Xóa một lần xuất hiện của m.
Trừ m từ tất cả các phần tử còn lại trong mảng.
Thao tác chỉ thực hiện khi mảng có kích thước > 1.

2. Phân tích mục tiêu:

Làm cho số nhỏ nhất trong mảng càng lớn càng tốt.
Có thể áp dụng thao tác nhiều lần (từ 0 đến n-1 lần).
Cần tìm giá trị lớn nhất của phần tử nhỏ nhất có thể đạt được sau một số thao tác.

3. Suy nghĩ về sự thay đổi của mảng:

Mỗi lần thao tác, kích thước mảng giảm đi 1.
Giá trị các phần tử thay đổi, nhưng sự sai khác giữa các phần tử còn lại sau khi trừ đi m vẫn giữ nguyên như sự sai khác giữa chúng trước khi trừ đi m. Ví dụ: (x - m) - (y - m) = x - y. Điều này gợi ý rằng các mối quan hệ về khoảng cách giữa các phần tử được bảo toàn.

4. Lợi ích của việc sắp xếp:

Nếu mảng ban đầu là [a1, a2, ..., an]. Sau khi sắp xếp, ta có a'_1 <= a'_2 <= ... <= a'_n.
Số nhỏ nhất luôn là a'_1.
Sau thao tác đầu tiên: Xóa a'_1, trừ a'_1 khỏi các phần tử còn lại. Mảng mới (về giá trị) sẽ chứa a'_2 - a'_1, a'_3 - a'_1, ..., a'_n - a'_1. Số nhỏ nhất trong mảng mới này là a'_2 - a'_1 (do a'_1 <= a'_2 <= ... <= a'_n nên a'_i - a'_1 >= a'_2 - a'_1 cho i >= 2).
Sau thao tác thứ hai: Số nhỏ nhất trong mảng hiện tại là a'_2 - a'_1. Xóa nó, trừ nó khỏi các phần tử còn lại. Các phần tử còn lại ban đầu là a'_3 - a'_1, a'_4 - a'_1, ..., a'_n - a'_1. Sau khi trừ đi a'_2 - a'_1, chúng trở thành (a'_i - a'_1) - (a'_2 - a'_1) = a'_i - a'_2 cho i = 3, ..., n. Số nhỏ nhất trong mảng mới này là a'_3 - a'_2.

5. Phát hiện quy luật:

Nếu ta luôn áp dụng thao tác trừ tối thiểu cho đến khi mảng chỉ còn 1 phần tử, thì các giá trị nhỏ nhất xuất hiện trong mảng ở đầu mỗi bước (trước khi thực hiện thao tác) sẽ lần lượt là:
- Ban đầu (0 thao tác): a'_1
- Sau 1 thao tác: a'_2 - a'_1
- Sau 2 thao tác: a'_3 - a'_2
- ...
- Sau k thao tác: a'_{k+1} - a'_k
- ...
- Sau n-1 thao tác (mảng chỉ còn 1 phần tử): a'_n - a'_{n-1}. Giá trị của phần tử duy nhất này chính là số nhỏ nhất của mảng cuối cùng.

6. Liên hệ với bài toán:

Bài toán yêu cầu tìm giá trị lớn nhất của phần tử nhỏ nhất sau khi áp dụng một số (có thể bằng 0) thao tác.
Điều này có nghĩa là ta có thể dừng lại sau 0 thao tác, 1 thao tác, 2 thao tác, ..., n-1 thao tác.
Giá trị nhỏ nhất của mảng sau 0, 1, 2, ..., n-1 thao tác lần lượt là a'_1, a'_2 - a'_1, a'_3 - a'_2, ..., a'_n - a'_{n-1}.
Mục tiêu là tìm giá trị lớn nhất trong tập hợp các giá trị này: { a'_1, a'_2 - a'_1, a'_3 - a'_2, ..., a'_n - a'_{n-1} }.

7. Thuật toán:

Đọc số lượng test case t.
Lặp t lần: a. Đọc kích thước mảng n. b. Đọc n phần tử vào một cấu trúc dữ liệu, ví dụ vector<int>. c. Nếu n == 1, kết quả là chính phần tử đó. In ra và chuyển sang test case tiếp theo. d. Sắp xếp mảng theo thứ tự tăng dần (sort). e. Khởi tạo biến max_min_value bằng phần tử đầu tiên của mảng đã sắp xếp (a[0]). Đây là giá trị nhỏ nhất sau 0 thao tác. f. Duyệt qua mảng đã sắp xếp từ phần tử thứ 2 đến hết (từ chỉ số 1 đến n-1). g. Với mỗi phần tử a[i], tính hiệu a[i] - a[i-1]. Đây chính là giá trị nhỏ nhất của mảng nếu ta thực hiện i thao tác (theo phân tích ở bước 5, nếu index bắt đầu từ 1 thì là k=i-1 thao tác). h. Cập nhật max_min_value bằng giá trị lớn nhất giữa max_min_value hiện tại và hiệu vừa tính (max). i. Sau khi duyệt xong, max_min_value sẽ chứa giá trị lớn nhất cần tìm. In ra max_min_value.

8. Các lưu ý khi cài đặt:

Sử dụng vector để lưu trữ mảng.
Sử dụng sort để sắp xếp mảng.
Sử dụng max để tìm giá trị lớn nhất.
Đảm bảo sử dụng kiểu dữ liệu đủ lớn cho các phần tử mảng (int là đủ theo ràng buộc -10^9 \le a_i \le 10^9). Hiệu hai số int cũng nằm trong phạm vi của int.
Đối với bài tập competitive programming, nên thêm ios_base::sync_with_stdio(false); cin.tie(NULL); để tăng tốc độ nhập xuất.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.