Bài 33.3: Danh sách liên kết đôi trong C++

Chào mừng trở lại với series C++! Hôm nay, chúng ta sẽ đào sâu vào một cấu trúc dữ liệu vô cùng linh hoạt và mạnh mẽ: Danh sách liên kết đôi (Doubly Linked List). Nếu bạn đã quen thuộc với danh sách liên kết đơn (singly linked list), thì danh sách liên kết đôi sẽ là một bước tiến thú vị, mang lại những khả năng mới.

Vậy, danh sách liên kết đôi là gì và nó khác gì so với danh sách liên kết đơn?

Khác biệt cốt lõi: Hai con trỏ!

Điểm khác biệt quan trọng nhất nằm ở mỗi phần tử (hay node) của danh sách. Trong danh sách liên kết đơn, mỗi node chỉ chứa dữ liệu và một con trỏ next (trỏ tới node kế tiếp). Ngược lại, trong danh sách liên kết đôi, mỗi node chứa dữ liệu và hai con trỏ:

  1. next: Con trỏ trỏ tới node kế tiếp trong danh sách.
  2. prev: Con trỏ trỏ tới node trước đó trong danh sách.

Chính sự tồn tại của con trỏ prev này mang lại những ưu điểm đáng kể, đặc biệt là khả năng duyệt danh sách theo cả hai chiều (từ đầu đến cuối và từ cuối về đầu) và thao tác xoá dễ dàng hơn trong nhiều trường hợp.

Hãy cùng xem cấu trúc của một node trong C++:

struct Node {
    int g;
    Node* n;
    Node* p;
    Node(int gt) : g(gt), n(nullptr), p(nullptr) {}
};

Giải thích code:

  • Chúng ta định nghĩa một struct tên là Node.
  • Nó có một thành viên data để lưu trữ dữ liệu (ở đây dùng int, bạn có thể dùng kiểu dữ liệu khác tùy ý).
  • next là một con trỏ kiểu Node*, trỏ đến node "đằng sau" nó.
  • prev là một con trỏ kiểu Node*, trỏ đến node "đằng trước" nó.
  • Constructor Node(int val) là một cách tiện lợi để tạo một node mới, gán giá trị val cho data và ban đầu đặt cả next lẫn prev là nullptr (chỉ báo rằng nó chưa liên kết với node nào khác).
Cấu trúc tổng thể của Danh sách liên kết đôi

Để quản lý toàn bộ danh sách, chúng ta thường sử dụng một lớp (class) hoặc struct chứa các con trỏ đặc biệt:

  • head: Con trỏ trỏ tới node đầu tiên của danh sách.
  • tail: Con trỏ trỏ tới node cuối cùng của danh sách.

Sự có mặt của con trỏ tail cũng là một điểm khác biệt so với danh sách liên kết đơn thông thường (mặc dù bạn có thể thêm tail vào danh sách đơn nếu cần). Việc có tail giúp các thao tác thêm/xoá ở cuối danh sách trở nên hiệu quả hơn rất nhiều (O(1)) thay vì phải duyệt toàn bộ danh sách từ đầu như trong danh sách đơn.

Lớp quản lý danh sách liên kết đôi có thể trông như thế này:

#include <iostream>

struct Node {
    int g;
    Node* n;
    Node* p;
    Node(int gt) : g(gt), n(nullptr), p(nullptr) {}
};

class DoublyLinkedList {
private:
    Node* h;
    Node* t;

public:
    DoublyLinkedList() : h(nullptr), t(nullptr) {}
    ~DoublyLinkedList();
    void themDau(int g);
    void themCuoi(int g);
    void xoa(int k);
    void hienThiXuoi() const;
    void hienThiNguoc() const;
    bool tim(int k) const;
};

DoublyLinkedList::~DoublyLinkedList() {
    Node* hienTai = h;
    while (hienTai != nullptr) {
        Node* keTiep = hienTai->n;
        delete hienTai;
        hienTai = keTiep;
    }
    h = nullptr;
    t = nullptr;
    cout << "DSLK doi da duoc huy." << endl;
}

// ... Triển khai các phương thức khác sẽ ở dưới ...

Giải thích code:

  • Lớp DoublyLinkedList chứa hai con trỏ head và tail, ban đầu được khởi tạo là nullptr trong constructor, biểu thị một danh sách rỗng.
  • Destructor ~DoublyLinkedList() là phần cực kỳ quan trọng. Vì chúng ta cấp phát bộ nhớ cho các node bằng new, chúng ta phải giải phóng chúng bằng delete khi không cần nữa để tránh rò rỉ bộ nhớ (memory leak). Destructor này duyệt qua toàn bộ danh sách và xoá từng node một cách an toàn.
Các thao tác cơ bản trên Danh sách liên kết đôi

Bây giờ, hãy đi sâu vào cách triển khai các thao tác phổ biến trên danh sách liên kết đôi.

1. Thêm node vào đầu danh sách (insertAtBeginning)

Thao tác này khá đơn giản, cần cập nhật con trỏ head và các liên kết của node mới cũng như node cũ ở đầu.

void DoublyLinkedList::themDau(int g) {
    Node* n = new Node(g);
    if (h == nullptr) {
        h = n;
        t = n;
    } else {
        n->n = h;
        h->p = n;
        h = n;
    }
    cout << "Da them " << g << " vao dau DSLK." << endl;
}

Giải thích code:

  1. Tạo một node mới với dữ liệu cần thêm. Con trỏ next và prev của nó ban đầu là nullptr (từ constructor Node).
  2. Kiểm tra danh sách rỗng: Nếu head là nullptr, tức danh sách chưa có phần tử nào, node mới chính là node đầu tiên và cũng là node cuối cùng. Cập nhật cả head và tail trỏ tới node mới.
  3. Danh sách không rỗng:
    • Con trỏ next của newNode sẽ trỏ tới node hiện đang là head.
    • Con trỏ prev của node hiện đang là head sẽ trỏ ngược về newNode.
    • Cập nhật head để nó trỏ tới newNode.
2. Thêm node vào cuối danh sách (insertAtEnd)

Thao tác này hiệu quả hơn nhiều so với danh sách đơn nhờ có con trỏ tail.

void DoublyLinkedList::themCuoi(int g) {
    Node* n = new Node(g);
    if (t == nullptr) {
        h = n;
        t = n;
    } else {
        n->p = t;
        t->n = n;
        t = n;
    }
    cout << "Da them " << g << " vao cuoi DSLK." << endl;
}

Giải thích code:

  1. Tạo một node mới.
  2. Kiểm tra danh sách rỗng: Giống như thêm vào đầu, node mới là head và tail.
  3. Danh sách không rỗng:
    • Con trỏ prev của newNode sẽ trỏ tới node hiện đang là tail.
    • Con trỏ next của node hiện đang là tail sẽ trỏ tới newNode.
    • Cập nhật tail để nó trỏ tới newNode.
3. Duyệt danh sách

Đây là lúc ưu điểm của danh sách đôi thể hiện rõ ràng: bạn có thể duyệt từ đầu hoặc từ cuối.

Duyệt xuôi (từ head đến tail) - displayForward 
void DoublyLinkedList::hienThiXuoi() const {
    if (h == nullptr) {
        cout << "DSLK rong." << endl;
        return;
    }
    Node* hienTai = h;
    while (hienTai != nullptr) {
        cout << hienTai->g << " <-> ";
        hienTai = hienTai->n;
    }
    cout << "nullptr" << endl;
}

Giải thích code:

  • Kiểm tra danh sách rỗng.
  • Bắt đầu từ head.
  • Lặp chừng nào current còn khác nullptr.
  • In dữ liệu của node current.
  • Cập nhật current bằng current->next để di chuyển tới node tiếp theo.
Duyệt ngược (từ tail về head) - displayBackward 
void DoublyLinkedList::hienThiNguoc() const {
     if (t == nullptr) {
        cout << "DSLK rong." << endl;
        return;
    }
    Node* hienTai = t;
    while (hienTai != nullptr) {
        cout << hienTai->g << " <-> ";
        hienTai = hienTai->p;
    }
    cout << "nullptr" << endl;
}

Giải thích code:

  • Kiểm tra danh sách rỗng.
  • Bắt đầu từ tail.
  • Lặp chừng nào current còn khác nullptr.
  • In dữ liệu của node current.
  • Cập nhật current bằng current->prev để di chuyển tới node trước đó. Đây là điểm khác biệt so với duyệt xuôi.
4. Tìm kiếm giá trị (search)

Thao tác này tương tự như danh sách đơn, chỉ cần duyệt từ đầu đến cuối và kiểm tra dữ liệu.

bool DoublyLinkedList::tim(int k) const {
    Node* hienTai = h;
    while (hienTai != nullptr) {
        if (hienTai->g == k) {
            return true;
        }
        hienTai = hienTai->n;
    }
    return false;
}

Giải thích code:

  • Bắt đầu từ head.
  • Lặp qua từng node.
  • Trong mỗi node, kiểm tra xem current->data có bằng key cần tìm không.
  • Nếu bằng, trả về true ngay lập tức.
  • Nếu duyệt hết danh sách mà không tìm thấy, vòng lặp kết thúc và trả về false.
5. Xoá node (deleteNode)

Xoá một node là nơi danh sách liên kết đôi thể hiện sự tiện lợi nếu bạn đã có con trỏ tới node cần xoá. Tuy nhiên, thường chúng ta cần xoá một node có giá trị cụ thể, nên trước tiên phải tìm node đó. Sau khi tìm thấy, việc cập nhật con trỏ next của node đứng trước và con trỏ prev của node đứng sau node bị xoá là cần thiết. Phải cẩn thận xử lý các trường hợp đặc biệt: xoá node đầu, xoá node cuối, xoá node duy nhất.

void DoublyLinkedList::xoa(int k) {
    Node* hienTai = h;
    while (hienTai != nullptr && hienTai->g != k) {
        hienTai = hienTai->n;
    }
    if (hienTai == nullptr) {
        cout << "Node " << k << " khong tim thay." << endl;
        return;
    }
    cout << "Dang xoa node: " << k << endl;

    if (hienTai->p != nullptr) {
        hienTai->p->n = hienTai->n;
    } else {
        h = hienTai->n;
    }

    if (hienTai->n != nullptr) {
        hienTai->n->p = hienTai->p;
    } else {
        t = hienTai->p;
    }

    if (h == nullptr) {
         t = nullptr;
    }
    delete hienTai;
}

Giải thích code:

  1. Duyệt từ đầu danh sách để tìm node có data bằng key.
  2. Nếu vòng lặp kết thúc mà current là nullptr, nghĩa là không tìm thấy node, in thông báo và kết thúc hàm.
  3. Nếu tìm thấy (current không phải nullptr):
    • Cập nhật con trỏ prev của node kế tiếp: Nếu node bị xoá không phải là node cuối cùng (current->next != nullptr), thì con trỏ prev của node đứng sau nó (current->next->prev) phải được cập nhật để trỏ tới node đứng trước node bị xoá (current->prev). Nếu node bị xoá là node cuối, cập nhật tail thành node đứng trước nó.
    • Cập nhật con trỏ next của node trước đó: Nếu node bị xoá không phải là node đầu tiên (current->prev != nullptr), thì con trỏ next của node đứng trước nó (current->prev->next) phải được cập nhật để trỏ tới node đứng sau node bị xoá (current->next). Nếu node bị xoá là node đầu, cập nhật head thành node đứng sau nó.
    • Trường hợp node duy nhất: Nếu sau khi xoá, head trở thành nullptr, điều đó có nghĩa là danh sách đã rỗng, nên tail cũng phải được đặt là nullptr.
  4. Cuối cùng, sử dụng delete current để giải phóng bộ nhớ mà node đó đang chiếm giữ.
Ví dụ minh hoạ đầy đủ

Kết hợp tất cả lại, đây là một ví dụ đơn giản sử dụng các thao tác đã triển khai:

#include <iostream>

struct Node {
    int g;
    Node* n;
    Node* p;
    Node(int gt) : g(gt), n(nullptr), p(nullptr) {}
};

class DoublyLinkedList {
private:
    Node* h;
    Node* t;

public:
    DoublyLinkedList() : h(nullptr), t(nullptr) {}
    ~DoublyLinkedList();
    void themDau(int g);
    void themCuoi(int g);
    void xoa(int k);
    void hienThiXuoi() const;
    void hienThiNguoc() const;
    bool tim(int k) const;
};

DoublyLinkedList::~DoublyLinkedList() {
    Node* hienTai = h;
    while (hienTai != nullptr) {
        Node* keTiep = hienTai->n;
        delete hienTai;
        hienTai = keTiep;
    }
    h = nullptr;
    t = nullptr;
    cout << "DSLK doi da duoc huy." << endl;
}

void DoublyLinkedList::themDau(int g) {
    Node* n = new Node(g);
    if (h == nullptr) {
        h = n;
        t = n;
    } else {
        n->n = h;
        h->p = n;
        h = n;
    }
    cout << "Da them " << g << " vao dau DSLK." << endl;
}

void DoublyLinkedList::themCuoi(int g) {
    Node* n = new Node(g);
    if (t == nullptr) {
        h = n;
        t = n;
    } else {
        n->p = t;
        t->n = n;
        t = n;
    }
    cout << "Da them " << g << " vao cuoi DSLK." << endl;
}

void DoublyLinkedList::xoa(int k) {
    Node* hienTai = h;
    while (hienTai != nullptr && hienTai->g != k) {
        hienTai = hienTai->n;
    }
    if (hienTai == nullptr) {
        cout << "Node " << k << " khong tim thay." << endl;
        return;
    }
    cout << "Dang xoa node: " << k << endl;

    if (hienTai->p != nullptr) {
        hienTai->p->n = hienTai->n;
    } else {
        h = hienTai->n;
    }

    if (hienTai->n != nullptr) {
        hienTai->n->p = hienTai->p;
    } else {
        t = hienTai->p;
    }

    if (h == nullptr) {
         t = nullptr;
    }
    delete hienTai;
}

void DoublyLinkedList::hienThiXuoi() const {
    if (h == nullptr) {
        cout << "DSLK rong.";
    } else {
        Node* hienTai = h;
        while (hienTai != nullptr) {
            cout << hienTai->g << " <-> ";
            hienTai = hienTai->n;
        }
        cout << "nullptr";
    }
     cout << endl;
}

void DoublyLinkedList::hienThiNguoc() const {
     if (t == nullptr) {
        cout << "DSLK rong.";
    } else {
        Node* hienTai = t;
        while (hienTai != nullptr) {
            cout << hienTai->g << " <-> ";
            hienTai = hienTai->p;
        }
        cout << "nullptr";
    }
    cout << endl;
}

bool DoublyLinkedList::tim(int k) const {
    Node* hienTai = h;
    while (hienTai != nullptr) {
        if (hienTai->g == k) {
            return true;
        }
        hienTai = hienTai->n;
    }
    return false;
}

int main() {
    DoublyLinkedList ds;

    ds.themCuoi(10);
    ds.themDau(5);
    ds.themCuoi(20);
    ds.themDau(1);
    ds.themCuoi(30);

    cout << "\n--- DSLK sau khi them ---" << endl;
    cout << "Duyet xuoi: ";
    ds.hienThiXuoi();
    cout << "Duyet nguoc: ";
    ds.hienThiNguoc();

    cout << "\n--- Tim kiem ---" << endl;
    int gtTim = 10;
    if (ds.tim(gtTim)) {
        cout << gtTim << " co trong DSLK." << endl;
    } else {
        cout << gtTim << " khong co trong DSLK." << endl;
    }
    gtTim = 100;
     if (ds.tim(gtTim)) {
        cout << gtTim << " co trong DSLK." << endl;
    } else {
        cout << gtTim << " khong co trong DSLK." << endl;
    }

    cout << "\n--- Xoa phan tu ---" << endl;
    ds.xoa(20);
    ds.xoa(1);
    ds.xoa(30);
    ds.xoa(100);

    cout << "\n--- DSLK sau khi xoa ---" << endl;
    cout << "Duyet xuoi: ";
    ds.hienThiXuoi();
    cout << "Duyet nguoc: ";
    ds.hienThiNguoc();

     ds.xoa(5);
     ds.xoa(10);

    cout << "\n--- DSLK sau khi xoa het ---" << endl;
    cout << "Duyet xuoi: ";
    ds.hienThiXuoi();
    cout << "Duyet nguoc: ";
    ds.hienThiNguoc();

    return 0;
}

Output:

Da them 10 vao cuoi DSLK.
Da them 5 vao dau DSLK.
Da them 20 vao cuoi DSLK.
Da them 1 vao dau DSLK.
Da them 30 vao cuoi DSLK.

--- DSLK sau khi them ---
Duyet xuoi: 1 <-> 5 <-> 10 <-> 20 <-> 30 <-> nullptr
Duyet nguoc: 30 <-> 20 <-> 10 <-> 5 <-> 1 <-> nullptr

--- Tim kiem ---
10 co trong DSLK.
100 khong co trong DSLK.

--- Xoa phan tu ---
Dang xoa node: 20
Dang xoa node: 1
Dang xoa node: 30
Node 100 khong tim thay.

--- DSLK sau khi xoa ---
Duyet xuoi: 5 <-> 10 <-> nullptr
Duyet nguoc: 10 <-> 5 <-> nullptr
Dang xoa node: 5
Dang xoa node: 10

--- DSLK sau khi xoa het ---
Duyet xuoi: DSLK rong.
Duyet nguoc: DSLK rong.
DSLK doi da duoc huy.

Giải thích code main:

  • Tạo một đối tượng list thuộc lớp DoublyLinkedList.
  • Sử dụng các phương thức insertAtEnd và insertAtBeginning để thêm các số vào danh sách.
  • Gọi displayForward và displayBackward để xem trạng thái danh sách từ hai chiều.
  • Sử dụng search để kiểm tra sự tồn tại của các giá trị.
  • Gọi deleteNode nhiều lần để minh hoạ việc xoá các node ở các vị trí khác nhau (giữa, đầu, cuối) và cả node không tồn tại.
  • Sau mỗi lần xoá, hiển thị lại danh sách để thấy sự thay đổi.
  • Khi chương trình kết thúc (return 0), đối tượng list nằm trong hàm main sẽ bị hủy, và destructor ~DoublyLinkedList() sẽ tự động được gọi để giải phóng toàn bộ bộ nhớ đã cấp phát cho các node, tránh rò rỉ bộ nhớ.
Ưu điểm và Nhược điểm của Danh sách liên kết đôi

Ưu điểm:

  • Duyệt hai chiều dễ dàng: Có thể đi từ head đến tail hoặc ngược lại một cách hiệu quả.
  • Xoá node hiệu quả hơn: Nếu bạn đã có con trỏ tới node cần xoá, việc cập nhật các liên kết chỉ mất thời gian O(1) (hằng số), không cần tìm node trước đó như trong danh sách đơn.
  • Thêm/Xoá ở cuối nhanh chóng: Nhờ có con trỏ tail, các thao tác này cũng chỉ mất thời gian O(1).

Nhược điểm:

  • Tốn bộ nhớ hơn: Mỗi node cần thêm một con trỏ (prev), do đó tốn bộ nhớ gấp rưỡi hoặc gấp đôi so với danh sách liên kết đơn (tùy thuộc vào việc lưu trữ dữ liệu).
  • Thao tác thêm/xoá phức tạp hơn: Cần cập nhật hai con trỏ (next và prev) cho mỗi node bị ảnh hưởng, thay vì chỉ một như trong danh sách đơn. Điều này dễ dẫn đến sai sót nếu không cẩn thận.
Khi nào sử dụng Danh sách liên kết đôi?

Bạn nên cân nhắc sử dụng danh sách liên kết đôi khi:

  • Bạn cần thường xuyên duyệt danh sách theo cả hai chiều.
  • Bạn cần thực hiện các thao tác thêm/xoá hiệu quả ở cả đầu và cuối danh sách.
  • Bạn cần khả năng xoá một node nhanh chóng khi đã có sẵn con trỏ tới node đó.

Tuy nhiên, trong nhiều trường hợp thực tế, thư viện chuẩn C++ (list) đã cung cấp một triển khai danh sách liên kết đôi tối ưu và an toàn. Bạn nên ưu tiên sử dụng list trừ khi bạn có lý do cụ thể để tự triển khai (ví dụ: để học tập, tối ưu hóa rất đặc thù, hoặc làm việc trong môi trường không có STL).

Sử dụng list (Thay thế thực tế)

Để hoàn thiện bức tranh, hãy xem cách sử dụng list đơn giản:

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    list<int> ds;

    ds.push_back(10);
    ds.push_front(5);
    ds.push_back(20);

    cout << "DS list: ";
    for (int gt : ds) {
        cout << gt << " <-> ";
    }
    cout << "nullptr" << endl;

    auto it = find(ds.begin(), ds.end(), 10);
    if (it != ds.end()) {
        ds.erase(it);
        cout << "Da xoa 10." << endl;
    }

    cout << "DS sau khi xoa 10: ";
    for (int gt : ds) {
        cout << gt << " <-> ";
    }
    cout << "nullptr" << endl;

    ds.pop_front();
    cout << "Sau khi pop_front: ";
     for (int gt : ds) {
        cout << gt << " <-> ";
    }
    cout << "nullptr" << endl;

    return 0;
}

Output:

DS list: 5 <-> 10 <-> 20 <-> nullptr
Da xoa 10.
DS sau khi xoa 10: 5 <-> 20 <-> nullptr
Sau khi pop_front: 20 <-> nullptr

Giải thích code list:

  • Sử dụng list<int> để tạo một danh sách các số nguyên.
  • push_back và push_front thêm phần tử vào cuối và đầu tương ứng.
  • Duyệt danh sách dễ dàng bằng range-based for loop.
  • Để xoá theo giá trị, bạn cần dùng find để lấy iterator tới phần tử đó, sau đó dùng phương thức erase của list với iterator này.
  • pop_front và pop_back xoá phần tử ở đầu và cuối.
  • Ưu điểm lớn nhất là list tự động quản lý bộ nhớ, bạn không cần lo lắng về new và delete.

Bài tập ví dụ: C++ Bài 21.A3: Vé vào hội chợ

Vé vào hội chợ

FullHouse Dev đang tổ chức một hội chợ ở FullHouseLand. Anh ấy muốn tham gia hội chợ cùng với N người bạn của mình. Anh ấy đã thu thập được K vé vào cửa. Liệu Anh ấy có thể vào hội chợ cùng với tất cả N người bạn của mình không?

Mỗi người cần một vé để vào hội chợ, và mỗi vé chỉ có thể được sử dụng bởi một người.

INPUT FORMAT

  • Dòng đầu tiên chứa số nguyên T — số lượng bộ test.
  • Mỗi bộ test gồm một dòng chứa hai số nguyên cách nhau bởi dấu cách N, K.

OUTPUT FORMAT

  • Với mỗi bộ test, in ra trên một dòng mới YES nếu Anh ấy có thể vào hội chợ cùng với tất cả N người bạn của mình và NO nếu không thể.

CONSTRAINTS

  • 1 ≤ T ≤ 100
  • 1 ≤ N, K ≤ 100
Ví dụ

Input

4
5 8
6 3
2 2
1 2

Output

YES
NO
NO
YES
Giải thích:

  • Test 1: Anh ấy cần 5 vé cho bạn bè và một vé cho mình, và anh ấy đã thu thập được 8 vé. Vì vậy, anh ấy sẽ có thể vào hội chợ cùng với tất cả bạn bè.

  • Test 2: Anh ấy cần 6 vé cho bạn bè và một vé cho mình, trong khi anh ấy chỉ thu thập được 3 vé. Vì vậy, anh ấy sẽ không thể vào hội chợ cùng với tất cả bạn bè, chỉ có ba người có thể vào hội chợ.

  • Test 3: Anh ấy cần 2 vé cho bạn bè và một vé cho mình, trong khi anh ấy chỉ thu thập được 2 vé. Vì vậy, hoặc Anh ấy hoặc một trong những người bạn của anh ấy không thể vào hội chợ.

  • Test 4: Anh ấy cần tổng cộng 2 vé, một cho mình và một cho bạn. Anh ấy đã thu thập được 2 vé. Vì vậy, anh ấy sẽ có thể vào hội chợ cùng với người bạn của mình. Chào bạn, đây là hướng dẫn giải bài "Vé vào hội chợ" bằng C++ một cách ngắn gọn, tập trung vào logic và sử dụng các thư viện chuẩn (std).

Bài toán yêu cầu xác định xem với số vé K có đủ cho "Anh ấy" và toàn bộ N người bạn của mình cùng vào hội chợ hay không.

Phân tích bài toán:

  1. Số người cần vé: Anh ấy là 1 người, và có N người bạn. Tổng cộng có 1 + N người cần vé.
  2. Điều kiện đủ vé: Để tất cả mọi người cùng vào được, số vé Anh ấy có (K) phải lớn hơn hoặc bằng tổng số người cần vé.
  3. Kết quả:
    • Nếu K đủ (tức là K >= 1 + N), in ra "YES".
    • Nếu K không đủ (tức là K < 1 + N), in ra "NO".

Hướng dẫn giải chi tiết:

  1. Bạn cần đọc số lượng bộ test T.
  2. Sử dụng một vòng lặp để xử lý T bộ test.
  3. Bên trong vòng lặp:
    • Đọc hai số nguyên N và K cho bộ test hiện tại.
    • Tính tổng số người cần vé: tong_nguoi = N + 1.
    • So sánh số vé Anh ấy có (K) với tổng số người cần vé (tong_nguoi).
    • Nếu K >= tong_nguoi, in ra "YES".
    • Ngược lại (nếu K < tong_nguoi), in ra "NO".
    • Đảm bảo sau mỗi kết quả "YES" hoặc "NO", xuống dòng (endl).

Các bước thực hiện trong code C++:

  1. Bao gồm header cần thiết cho nhập xuất, ví dụ: <iostream>.
  2. Sử dụng int main() { ... }.
  3. Khai báo biến T và đọc giá trị của nó.
  4. Sử dụng vòng lặp while (T--) hoặc for (int i = 0; i < T; ++i) để lặp T lần.
  5. Bên trong vòng lặp, khai báo biến N và K, đọc giá trị của chúng.
  6. Sử dụng câu lệnh điều kiện if-else để so sánh K với N + 1.
  7. Sử dụng cout để in ra "YES" hoặc "NO" và endl để xuống dòng.

Lưu ý:

  • Sử dụng các kiểu dữ liệu số nguyên phù hợp cho N và K (ví dụ: int).
  • Không cần sử dụng các cấu trúc dữ liệu phức tạp, chỉ cần đọc, tính toán đơn giản và so sánh.
  • Ưu tiên sử dụng các hàm và đối tượng từ namespace std (cin, cout, endl).
#include <iostream>

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        if (k >= n + 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

Output:

YES
NO
NO
YES

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

Comments

There are no comments at the moment.