Lời mở đầu

Trong thế giới lập trình, ngoài các cách xử lý với những dữ liệu ta có (bằng những thuật toán) để được đầu ra mong muốn, ta còn có các cách để tổ chức dữ liệu. Một cách tổ chức dữ liệu được gọi là Cấu trúc Dữ liệu (CTDL). Trước hết, ta cần phân biệt rõ các Cấu trúc Dữ liệu được đề cập trong bài viết đóng vai trò là công cụ để xây dựng bài toán, còn Giải thuật về các Cấu trúc Dữ liệu (Data Structures & Algorithms) là thuộc phạm vi kiến thức khác.

Thế tại sao ta cần tổ chức dữ liệu một cách hợp lý?

Tưởng tượng bạn có một hàng sách lộn xộn trên kệ sách, bạn cần tìm quyển "Tây Du Ký", bạn phải lướt qua từng quyển một để tìm. Tuy nhiên, nếu cũng là hàng sách đó nhưng đã được sắp xếp theo thứ tự chữ cái đầu, bạn có thể truy tìm rất nhanh bằng cách liên tục thu hẹp vùng tìm kiếm của mình lại. Thực chất, việc bạn tìm và liên tục thu hẹp vùng của mình chính là một thuật toán, và hàng sách đã được sắp xếp của bạn chính là một CTDL. CTDL bổ trợ cho thuật toán, và thuật toán tận dụng các CTDL để chạy nhanh hơn.

Lại ví dụ về hàng sách, giả sử ngoài việc lấy sách ra thì bạn cũng muốn nhét sách vào lại. Việc bạn để cuốn sách đó ở cuối sẽ khiến hàng sách trở nên lộn xộn, nhưng nếu bạn muốn để sách lại ở vị trí dự định của nó thì bạn sẽ phải mất công đẩy từng cuốn sách một đằng trước (hoặc sau) chỗ đó để có chỗ nhét vào. Một cách khác là bạn có thể mua 26 cái kệ cho 26 chữ cái, khi đó việc để sách lại trở nên dễ dàng hơn và khi tìm bạn cũng chỉ cần tìm trong cái kệ có chữ cái tương ứng là được. Tuy nhiên làm như thế sẽ tốn rất nhiều diện tích và không khả thi với các căn nhà nhỏ. Cũng như thế, các CTDL đều có những ưu và nhược điểm của mình, về mặt không gian, thời gian, hay tuỳ mục đích sử dụng khác nhau.

Để giỏi CTDL không chỉ cần phải biết nhiều mà phải còn hiểu sâu và biết áp dụng linh động các CTDL dựa trên mục đích mong muốn của mình.

Các cấu trúc dữ liệu đơn giản

1. Mảng (Array)

Hãy xét một bài toán nhỏ như sau: Cho ~N~ số, hãy tính tổng của chúng.

Nếu đây là tổng 2 số, bạn có thể khai báo trước 2 biến int rồi tính tổng của chúng. Nhưng với ~N~ số chúng ta có 2 vấn đề: Chúng ta không hề biết trước ~N~ và kể cả có biết thì ~N~ có thể rất lớn, không thể nào khai báo tay được. Đây là khi ta cần dùng mảng.

Mảng là một dãy các phần tử được xếp tuần tự. Mỗi phần tử của mảng sẽ có một chỉ số và được đánh số từ bé đến lớn. Tuỳ vào ngôn ngữ sử dụng mà cách đánh số này sẽ khác nhau, tuy nhiên các số được đánh luôn liên tiếp nhau.

Khai báo trong C++: type name[number of elements] với type là kiểu phần tử, name là tên mảng và number of elements là số phần tử của mảng.

• Ví dụ: int mang[10] khai báo một mảng gồm 10 phần tử kiểu số nguyên.
• Mảng một khi đã khai báo thì không thể đổi số phần tử và kiểu phần tử, các phần tử cũng chỉ sử dụng chung một kiểu phần tử. Bạn không thể dùng một mảng số nguyên để lưu một ký tự, và cũng không thể thêm quá số phần tử đã khai báo.
• C++ đánh số mảng từ 0 đến (số phần tử - 1). Phần tử đầu tiên của mảng int mang[10] sẽ là mang[0] và phần tử cuối cùng sẽ là mang[9].

2. Mảng động (Dynamic array)

Cũng bài toán trên, nhưng họ không cho bạn trước số phần tử. Lúc này bạn sẽ cần dùng tới mảng động.

Mảng động là mảng nhưng bạn có thể thêm / bớt phần tử tuỳ ý. Một số ngôn ngữ còn cho phép bạn thêm các phần tử khác kiểu vào trong mảng (như Python). Tuy nhiên C++ không cho phép điều đấy (tức bạn chỉ được thêm vào phần tử cùng kiểu với mảng), ngoài ra các tính chất còn lại của mảng động đều tương tự mảng.

Khai báo trong C++: vector<type> name với type là kiểu phần tử và name là tên mảng.

• Ví dụ: vector<int> mang_dong cho một mảng động mới tên mang_dong và mang kiểu int.
• Mảng động ban đầu khai báo sẽ rỗng, nếu bạn muốn mảng động có sẵn các phần tử thì có thể khai báo vector<type> name(number of elements), ví dụ như vector<int> mang_dong(10).

Ngoài các tính chất như mảng thông thường, C++ còn có các hàm riêng dành cho vector. Giả sử có một mảng động vec kiểu int và có ~N~ phần tử.

• vec.size() sẽ cho biết kích thước của mảng, cụ thể là ~N~. Độ phức tạp ~O(1)~.
• vec.push_back(value) sẽ thêm một phần tử mang giá trị value vào cuối mảng, value phải cùng kiểu với mảng. Độ phức tạp ~O(1)~.
• Ngoài ra còn hàm insert() và hàm erase() cho phép bạn thêm & xoá phần tử ở bất kỳ vị trí nào, nhưng chúng yêu cầu hiểu biết về con trỏ (sẽ được nói ở blog sau) và có độ phức tạp lên đến ~O(N)~.

3. Chuỗi / xâu (String)

Chuỗi là một dãy các ký tự liên tiếp. Có thể nói rằng chuỗi là một mảng động mang kiểu ký tự. Trong C++ cách làm việc trên chuỗi gần như tương đồng với vector<char>.

Khai báo trong C++: string name với name là tên của chuỗi.

• Ví dụ: string S cho một chuỗi mới tên S.
• Có thể đặt trước giá trị cho chuỗi luôn bằng cách sử dụng toán tử =: string S = "abc".

Các thao tác và hàm bổ trợ của string gần như tương đồng với vector<char>. Tuy nhiên string cũng có một số cách làm việc riêng.

• Việc sử dụng toán tử + cho 2 chuỗi sẽ cho một chuỗi mới là chuỗi nối lại của 2 chuỗi cũ. Với S = "abc" và T = "def" thì S + T sẽ cho "abcdef". Độ phức tạp của phép tính này là ~O(|S| + |T|)~ với ~|S|~ và ~|T|~ là độ dài của 2 chuỗi S và T.
• Tương tự thế, sử dụng toán tử += sẽ gắn chuỗi cộng vào đằng sau chuỗi hiện tại. Với S = "abc" và T = "def" thì S += T sẽ khiến chuỗi S thành "abcdef". Lưu ý rằng độ phức tạp của phép tính này là ~O(|T|)~, không phải là ~O(|S| + |T|)~ như trên.

Các cấu trúc dữ liệu trong thư viện chuẩn C++

Trong C++ có một thư viện mang tên STL (Standard Template Library) - thư viện chuẩn C++. Thư viện này hỗ trợ các CTDL vô cùng mạnh mẽ và tiện lợi mà Pascal không có và yêu cầu người dùng tự cài đặt lại. STL còn hỗ trợ cả một số thuật toán nhưng sẽ không được đề cập ở đây. Bản thân vector và string cũng là các thành phần trong thư viện chuẩn này, tuy nhiên do bản chất đơn giản nó đã được xếp chung với mảng ở mục trên.

1. Pair (Cặp)

C++ cho phép bạn "cặp" hai kiểu lại với nhau để tạo thành một kiểu mới mang 2 kiểu và 2 giá trị khác nhau. Điều này đặc biệt hữu dụng khi bạn cần một mảng mà mỗi phần tử lưu giá trị và số thứ tự mà không cần khai báo 2 mảng khác nhau, hoặc làm việc với toạ độ điểm trên không gian ~Oxy~.

Khai báo trong C++: pair<type_1, type_2> name với type_1 là kiểu của giá trị đầu tiên, type_2 là kiểu của giá trị thứ hai và name là tên biến.

• Ví dụ: Để khai báo một biến có thể lưu tên một người và số thứ tự của người đó có thể dùng pair<string, int> person.
• Cũng như thế, có thể khai báo một danh sách người mang tên và số thứ tự bằng việc sử dụng mảng / mảng động: vector<pair<string, int>> person_list.

Cách làm việc: Bạn có thể dùng .first để truy cập vào giá trị đầu tiên của pair và .second để truy vập vào giá trị thứ hai.

• Ví dụ bạn có pair<string, int> person. person.first cho bạn truy cập vào phần string của pair và bạn có thể dùng person.first như một string bình thường, tương tự vậy person.second có thể dùng như một biến int bình thường.

Để làm việc với các điểm trong toạ độ người ta thường dùng pair<int, int> để lưu điểm. Việc sử dụng 2 biến số nguyên riêng biệt cho một điểm là không khuyến khích vì dễ gây nhầm lẫn. Tuyệt đối không đặt tên các biến theo điểm là x1 y1 x2 y2, trên một số máy y1 là một hàm có thật và sẽ gây lỗi. Tốt hơn hết vẫn nên dùng pair.

Ngoài pair ra nếu bạn muốn sử dụng cặp 3 kiểu hoặc hơn với nhau bạn có thể dùng tuple (link) hoặc tự tạo struct.

2. Set (Tập hợp)

Set là một kiểu tập hợp. Như cái tên của nó, set là một CTDL cho phép bạn lưu một tập hợp các phần tử nào đấy không trùng nhau và theo thứ tự được định nghĩa (mặc định là từ bé đến lớn). set trong C++ cũng có thể lưu các kiểu phần tử khác ngoài số nguyên, miễn là các phần tử trong đấy cùng kiểu.

Khai báo trong C++: set<type> name với type là kiểu giá trị và name là tên tập hợp.

• Ví dụ: set<int> s sẽ cho bạn một tập hợp kiểu int tên s.

Cách làm việc: Vì cũng là một thành viên của STL nên set cũng có chung các hàm với vector nhưng cách dùng chúng lại hơi khác một tí.

• s.size() sẽ trả về kích cỡ hiện tại của tập hợp, độ phức tạp ~O(1)~.

• s.insert(value) sẽ thêm một phần tử mang giá trị value vào trong tập hợp s nếu chưa có. Lưu ý rằng hàm insert này không có con trỏ chỉ đến vị trí, vì đây là tập hợp nên ta cũng không cần quan tâm vị trí. Độ phức tạp ~O(\log{N})~.

• s.erase(value) sẽ xoá đi phần tử mang giá trị value trong tập hợp nếu có. Cũng như insert, vì đây là tập hợp nên ta không cần quan tâm đến con trỏ hay vị trí muốn xoá mà chỉ cần biết số muốn xoá là đủ. Độ phức tạp ~O(\log{N})~.

• s.count(value) sẽ đếm số phần tử mang giá trị value trong tập hợp. Vì trong tập hợp không chứa các phần tử trùng nhau nên hàm này thường sẽ chỉ trả về 0 (nếu không có) hoặc 1 (nếu có), nên có thể dùng như một cách để xem value có trong tập hợp hay không. Độ phức tạp ~O(\log{N})~.

• Ngoài ra còn có thể duyệt các phần tử của tập hợp bằng cách ghi for(type i : s) với type là kiểu của tập hợp s (trong trường hợp này là int). Biến i ở đây sẽ mang giá trị của chính các phần tử trong tập hợp trong quá trình duyệt. Tập hợp là một kiểu không có vị trí nên không thể nào sử dụng cách for(int i = 0; i < n; ++i) như truyền thống để duyệt được. Độ phức tạp quá trình duyệt cả tập hợp là ~O(N)~ với ~N~ là s.size().

Có thể thấy sức mạnh của set nằm ở việc các thao tác với nó (chèn, xoá, tìm) có tốc độ thực thi rất nhanh, nhanh hơn nhiều nếu so với một mảng hoặc vector lưu một tập hợp số tương tự. Một số ứng dụng của set có thể bao gồm tìm phần tử / phần tử gần nhất trong một tập hợp cho sẵn, đếm số phần tử riêng biệt trong mảng,... Tập hợp trong C++ ngoài set ra còn một số biến thể khác, với chức năng và công dụng khác nhau, chúng sẽ được nói ở blog sau.

3. Map (Ánh xạ)

Trước khi đi vào map hãy cùng nói về ánh xạ. Ánh xạ là một quy tắc nối cho 2 tập hợp ~A~ và ~B~ nào đấy sao mỗi các phần tử của tập ~A~ chỉ nối với một phần tử duy nhất của tập ~B~ (mỗi phần tử tập ~B~ có thể được nối bởi nhiều phần tử tập ~A~). Một ví dụ đơn giản và gần gũi của ánh xạ là một hàm số ~f(x)~ nào đó. Đây là ánh xạ của một tập số với một tập số, và ~f(x)~ chỉ cho một đầu ra duy nhất với mỗi ~x~.

Kiểu dữ liệu của một ánh xạ trong C++ là map. Trong map ta sẽ có các khoá và các giá trị tương ứng với các khoá đó. Mỗi khoá chỉ mang một giá trị duy nhất, theo định nghĩa của ánh xạ. Đương nhiên ánh xạ không chỉ giới hạn giữa tập số, ví dụ các khoá của bạn có thể là tên (chuỗi) hoặc một kiểu bất kỳ nào đấy.

Khai báo trong C++: map<type_1, type_2> name với type_1 là kiểu của khoá, type_2 là kiểu của giá trị và name là tên của map.

• Ví dụ: map<string, int> mp sẽ cho bạn một map tên mp với khoá mang kiểu string và giá trị mang kiểu int.

Cách làm việc: Cách làm việc của map lại có đôi phần giống mảng, trong khi vẫn hỗ trợ một số hàm của set.

• Để truy cập một khoá ta dùng mp[key] với key là khoá. Nếu khoá này đã được tạo nó sẽ mang giá trị đã được gán trước đó, nếu không nó sẽ được tạo với giá trị mặc định của kiểu giá trị đó. Ví dụ khi ta ghi mp["hello"] khoá "hello" chưa có trong mp và sẽ được tạo mới với số 0 (đây là giá trị mặc định của kiểu int). Độ phức tạp ~O(\log{N})~.

• Để tìm xem một khoá đã có trong mp hay không ta dùng mp.count(key) với key là khoá. Cũng như set, vì mỗi khoá chỉ mang một giá trị nên mỗi khoá chỉ xuất hiện tối đa một lần, hàm này chỉ trả về 0 hoặc 1. Không dùng mp[key] != 0 để kiểm tra xem khoá có trong mp hay không, mỗi lần làm như vậy sẽ tạo thêm một khoá key mới và nếu dùng quá nhiều có thể gây MLE (vì đầy bộ nhớ) hoặc TLE (vì mp quá nhiều khoá nên truy xuất chậm). Độ phức tạp ~O(\log{N})~.

• Để xoá một khoá trong mp ta dùng mp.erase(key) với key là khoá. Không dùng mp[key] = 0 để xoá khoá vì thực chất làm vậy là đang đặt lại giá trị của khoá thành 0 chứ không thực sự xoá nó ra khỏi mp. Độ phức tạp ~O(\log{N})~.

• Một ánh xạ sẽ lưu các phần tử theo từng cặp {khoá, giá trị} nên để duyệt ánh xạ ta sẽ dùng pair của 2 kiểu khoá và giá trị. Để duyệt mp ta sẽ dùng for(pair<string, int> i : mp), khi đó với mỗi lần duyệt i sẽ là một cặp với biến đầu tiên là khoá và biến thứ hai là giá trị của khoá đó. Để làm việc với phần tử đó ta có thể dùng như kiểu pair bình thường. Độ phức tạp ~O(N)~.

map thường được dùng nhiều nhất trong các trường hợp cần dùng truy cập mảng với chỉ số rất lớn mà không thể khai báo mảng tới mức đó được. Giả sử bạn cần truy cập phần tử thứ ~10^9~, việc dùng map khi đó sẽ chỉ lưu tại các vị trí có truy cập thôi (vị trí mp[1000000000]) mà không cần tạo ra từng phần một như khai báo một mảng ~10^9~ phần tử. Việc ánh xạ cũng có thể mang nhiều ý nghĩa khác, như đánh số cho tên trong một danh sách nào đó bằng map<string, int>, lưu số lần xuất hiện các số ~x~ trong mảng bằng map<int, int> (đặc biệt hữu dụng khi số trong mảng lớn),...

Như set, map cũng có một số biến thể của mình và sẽ được đề cập ở blog sau.

4. Stack (Ngăn xếp)

Tưởng tượng bạn có một chồng đĩa xếp thẳng đứng. Rõ ràng bạn chỉ có thể lấy một cái đĩa ở trên đầu hiện tại. Bạn đặt đĩa nào vào trước thì nó sẽ nằm ở dưới, và để lấy được nó bạn phải lấy nó ra sau khi lấy hết tất cả các cái đĩa ở trên. Ngăn xếp là một cấu trúc dữ liệu ngăn xếp dựa trên nguyên lý đấy (Last In First Out - LIFO). Một ngăn xếp cho phép các thao tác sau: thêm một phần tử vào cuối, đọc phần tử ở cuối và xoá phần tử ở cuối đi.

Khai báo trong C++: stack<type> name với type là kiểu và name là tên của ngăn xếp.

• Ví dụ: stack<int> st sẽ khai báo một ngăn xếp mới tên st với kiểu int.

Cách làm việc: Ngăn xếp hỗ trợ các hàm sau đây:

• st.push(value): Thêm một phần tử mới mang giá trị value vào đỉnh của st. Độ phức tạp ~O(1)~.
• st.top(): Lấy giá trị của phần tử trên cùng của st. Hàm này sẽ gây lỗi nếu không có phần tử trong hàng đợi, hãy cẩn thận khi dùng. Độ phức tạp ~O(1)~.
• st.pop(): Xoá phần tử trên cùng của st. Hàm này sẽ gây lỗi nếu không có phần tử trong hàng đợi, hãy cẩn thận khi dùng. Độ phức tạp ~O(1)~.

Tuy là một cấu trúc đơn giản nhưng stack lại có những ứng dụng vô cùng ảo ma, các bạn có thể đọc thêm tại VNOI Wiki.

5. Queue / Deque (Hàng đợi / Hàng đợi 2 đầu)

Ngược với ngăn xếp, Hàng đợi là một cấu trúc dữ liệu cho phép bạn lấy các phần tử theo thứ tự mà bạn đã cho chúng vào (First In First Out - FIFO). Cơ chế làm việc của nó dựa trên một "hàng đợi", ai vào hàng trước thì sẽ được tính tiền trước. Để lấy theo thứ tự đó thì phần tử sẽ được lấy từ đầu của hàng đợi thay vì từ cuối giống ngăn xếp.

Ngoài Stack vào Queue ra còn Deque (Double-ended queue) là một hàng đợi hai đầu, tức bạn có thể nhét và lấy phần tử từ cả 2 đầu của hàng đợi.

Khai báo trong C++:

• queue<type> name sẽ khai báo một hàng đợi mới mang kiểu type và tên name, ví dụ như queue<int> q.
• deque<type> name sẽ khai báo một hàng đợi 2 đầu mới mang kiểu type và tên name, ví dụ như deque<int> dq.

Cách làm việc trong C++: Với queue sẽ hỗ trợ một số hàm như sau:

• q.push(value): Thêm một phần tử mang giá trị value ở cuối.
• q.front(): Lấy giá trị của phần tử đầu tiên trong hàng đợi. Hàm này sẽ gây lỗi nếu không có phần tử trong hàng đợi, hãy cẩn thận khi dùng.
• q.pop(): Xoá phần tử đầu tiên trong hàng đợi. Hàm này sẽ gây lỗi nếu không có phần tử trong hàng đợi, hãy cẩn thận khi dùng.

Vì deque có 2 đầu nên các hàm của deque cũng sẽ hơi khác queue một tí.

• dq.push_front(value): Thêm một phần tử mang giá trị value ở đầu. Lưu ý rằng deque không có hàm push.
• dq.push_back(value): Thêm một phần tử mang giá trị value ở cuối.
• dq.front(): Lấy giá trị của phần tử đầu tiên trong hàng đợi. Hàm này sẽ gây lỗi nếu không có phần tử trong hàng đợi, hãy cẩn thận khi dùng.
• dq.back(): Lấy giá trị của phần tử cuối cùng trong hàng đợi. Hàm này sẽ gây lỗi nếu không có phần tử trong hàng đợi, hãy cẩn thận khi dùng.
• dq.pop_front(): Xoá một phần tử ở đầu hàng đợi. Lưu ý rằng deque không có hàm pop. Hàm này sẽ gây lỗi nếu không có phần tử trong hàng đợi, hãy cẩn thận khi dùng.
• dq.pop_back(): Xoá một phần tử ở cuối hàng đợi. Hàm này sẽ gây lỗi nếu không có phần tử trong hàng đợi, hãy cẩn thận khi dùng.

Độ phức tạp của tất cả các hàm trên (của queue lẫn deque) là ~O(1)~. Như stack, queue và deque cũng có những cách áp dụng rất ảo ma, bạn có thể đọc thêm tại VNOI Wiki.

Một số bài tập củng cố

Codeforces 1703D - Double Strings

Tóm tắt đề: Cho ~N~ xâu có độ dài tối đa là 8, với mỗi xâu ~s~ hãy cho biết có cách chọn hai xâu ~u~ và ~v~ trong dãy rồi ghép lại sao cho tạo được ~s~ hay không. Có thể chọn hai xâu ~u~ và ~v~ như nhau.

Ý tưởng: Hãy bắt đầu bằng cách tiếp cận trâu bò. Với mỗi xâu ~s~ ta sẽ lần lượt chia đôi nó tại từng vị trí thành hai xâu ~s_1~ và ~s_2~, rồi với mỗi xâu ~s_1~ và ~s_2~ ta tìm xem chúng có bằng xâu nào trong ~N~ xâu đã cho hay không. Độ phức tạp của cách làm này là ~O(|S| * N ^ 2)~ với ~|S|~ là độ dài một xâu. Ta có thể viết lại thành ~O(N ^ 2)~ vì độ dài mỗi xâu có thể coi như một hằng số (tối đa là 8). Rõ ràng độ phức tạp này vẫn chưa đủ nhanh để giải quyết bài toán với ~N \le 10 ^ 5~.

Cải tiến: Nhận xét rằng phần tìm xâu ~s_1~ và ~s_2~ trong dãy là phần lâu nhất, vì mỗi lần tìm ta lại phải duyệt nguyên dãy để tìm xem có xâu nào bằng hay không. Ta có thể đẩy nhanh quá trình tìm kiếm bằng set: Đầu tiên ta cho hết tất cả các xâu vào trong set, rồi với mỗi lần tìm ~s_1~ và ~s_2~ ta chỉ cần gọi hàm count() để coi nó có nằm trong set hay không. Cách làm này giảm độ phức tạp của mỗi lần tìm xuống ~O(\log{N})~, và làm bài toán chạy đủ nhanh trong ~O(N * \log{N})~.

USACO 2017 January Bronze - Don't be last!

Tóm tắt đề: Cho thông tin về ~N~ đợt vắt sữa, mỗi đợt vắt sữa cho biết tên con bò được vắt và lượng sữa mà nó vắt ra, hãy tìm tên con bò có lượng sữa được vắt ra sau các đợt vắt ít thứ nhì.

Ý tưởng: Ta cần một cách để dùng tên để lưu số lần vắt sữa. Người ta cho tên thay vì số nên việc dùng mảng ở đây sẽ trở nên khó khăn (bạn có thể tìm một cách để chuyển từ chuỗi sang số rồi lưu bằng mảng nhưng cài đặt tương đối mệt). Thay vào đó ta sẽ dùng map, cụ thể là map<string, int> mp để có thể dùng tên lưu số lần vắt sữa. Mỗi lần đọc tên vào (là một xâu s) và lượng sữa vắt ra ta chỉ cần cộng số lần vắt sữa đó vào mp[s].

Việc cần làm sau đó là tìm nhân vật có lượng sữa ít thứ nhì. Ta có thể làm bằng cách ta tạo thêm một map mới là map<int, string> mp2, rồi sau đó duyệt qua cái mp để với mỗi lượng sữa thì ta lưu cái tên tương ứng trong mp2. Trước khi gán vào lượng sữa đó trong mp2 ta có thể dùng hàm count() để kiểm tra xem lượng sữa đó đã có cái tên nào khác hay chưa, nếu có rồi thì ta lưu luôn là "Tie" thay vì lưu xâu tên vào. Cuối cùng ta có thể duyệt qua mp2, duyệt đúng 2 lần (vì ta đang cần tìm con bò có lượng sữa ít thứ nhì) rồi ghi ra luôn. Độ phức tạp sẽ là ~O(N * \log{N})~.

Lưu ý rằng ta không thể duyệt thẳng trong mp được, vì các phần tử được sắp xếp theo khoá (tức phần string trong trường hợp này) và ta cần phải tạo map mới để có thể lưu ngược lại rồi duyệt. Ngoài ra cũng cần phải cẩn thận xử lý các trường hợp đặc biệt (tất cả các con bò đều cho lượng sữa bằng nhau). Một con bò duy nhất có cho sữa cũng được xem là ít thứ hai vì ít nhất là những con bò vắng mặt (tức không cho sữa).

Bài này khá lằng nhằng nên mình có để lại phần code ở đây.

Một số bài tập khác

• Bedao Mini Contest 07 - RATE
• AtCoder Beginner Contest 261C - NewFolder(1)
• Codeforces 1722C - Word Game
• Codeforces 1611C - Polycarp Recovers the Permutation

Gợi ý các bài, cố gắng đừng đọc trừ khi bạn thật sự rất bí:

Bài 1: Dùng vector<string>
Bài 2: Dùng map<string, int>
Bài 3: Dùng map<string, int>
Bài 4: Dùng deque<int>

---

Author: Phan Hải Minh (water)