Bài 10: Struct, pair và sắp xếp theo nhiều tiêu chí trong C++ và Python (hàm so sánh cmp, xếp hạng)
Lời mở đầu
Ở bài 6 ta đã sắp xếp được một dãy số. Nhưng đề thi hiếm khi chỉ có số trần trụi: “Cho danh sách $n$ học sinh gồm họ tên và điểm, hãy in bảng xếp hạng theo điểm giảm dần, ai bằng điểm thì xếp theo tên”. Nếu dùng hai mảng riêng ten[] và diem[], mỗi lần đổi chỗ điểm lại phải nhớ đổi chỗ cả tên, rất dễ sai. Bài này giới thiệu struct (kiểu dữ liệu tự định nghĩa) và pair để gom nhiều thông tin thành một, rồi dùng sort kèm hàm so sánh để sắp xếp theo bất kỳ tiêu chí nào. Đây là dạng bài xuất hiện cực nhiều trong đề học sinh giỏi.
key= trong Python); sắp xếp kèm chỉ số ban đầu; xếp hạng có đồng hạng. Có khung chạy tay từng phép so sánh, mô phỏng “bảng xếp hạng” tự chọn tiêu chí và 8 bài tập kèm gợi ý.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Struct: tự tạo kiểu dữ liệu của riêng mình
struct (cấu trúc) cho phép em định nghĩa một kiểu dữ liệu mới gồm nhiều trường (thành phần). Ví dụ kiểu HocSinh gồm họ tên, điểm và tuổi. Sau khi định nghĩa, HocSinh dùng giống hệt int hay string: khai báo biến, khai báo mảng, truyền vào hàm… Truy cập từng trường bằng dấu chấm: hs.ten, hs.diem.
Struct gom các thông tin của một đối tượng thành một khối. Mảng struct là dãy các khối đó.
Code C++ và Python
#include <iostream>
#include <string>
using namespace std;
struct HocSinh { // định nghĩa kiểu mới, nhớ dấu ; ở cuối
string ten;
double diem;
int tuoi;
};
int main(){
HocSinh hs; // khai báo 1 biến kiểu HocSinh
hs.ten = "An"; hs.diem = 8.5; hs.tuoi = 15;
HocSinh b = {"Binh", 9.0, 14}; // gán nhanh theo đúng thứ tự các trường
cout << b.ten << " " << b.diem << endl;
HocSinh a[100]; // mảng 100 học sinh
a[0] = hs;
cout << a[0].ten;
return 0;
}from dataclasses import dataclass
@dataclass
class HocSinh: # Python dùng class (hoặc đơn giản là tuple)
ten: str
diem: float
tuoi: int
hs = HocSinh("An", 8.5, 15)
b = HocSinh("Binh", 9.0, 14)
print(b.ten, b.diem)
a = [hs, b] # list các học sinh
print(a[0].ten)
# Cách gọn hơn hay dùng khi thi: tuple ("An", 8.5, 15), truy cập bằng chỉ số t[0], t[1]Ví dụ: nhập $n$ học sinh, mỗi học sinh gồm tên (một từ) và điểm. In ra học sinh có điểm cao nhất (nếu nhiều bạn bằng nhau, in bạn nhập trước). Nhờ struct, ta chỉ cần nhớ vị trí của học sinh giỏi nhất là có đủ cả tên lẫn điểm:
Code C++ và Python
#include <iostream>
#include <string>
using namespace std;
struct HocSinh {
string ten;
int diem;
};
HocSinh a[1005];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i].ten >> a[i].diem;
int vt = 0;
for(int i = 1; i < n; i++){
if(a[i].diem > a[vt].diem)
vt = i;
}
cout << a[vt].ten << " " << a[vt].diem;
return 0;
}n = int(input())
a = []
for _ in range(n):
ten, diem = input().split()
a.append((ten, int(diem)))
vt = 0
for i in range(1, n):
if a[i][1] > a[vt][1]:
vt = i
print(a[vt][0], a[vt][1])Phần 2pair: struct có sẵn gồm hai thành phần
Rất nhiều khi ta chỉ cần gom hai giá trị: tọa độ $(x, y)$, (điểm, chỉ số), (giá trị, số lần xuất hiện)… C++ có sẵn kiểu pair<kiểu1, kiểu2> trong thư viện <utility> (đã có sẵn trong <bits/stdc++.h>), hai thành phần tên là .first và .second. Điều đặc biệt nhất: hai pair so sánh được với nhau theo kiểu “từ điển”: so first trước, nếu bằng nhau mới so second. Vì vậy sort một mảng pair sẽ tự sắp theo first tăng dần, bằng thì theo second tăng dần, không cần viết gì thêm.
Ví dụ: sắp xếp $n$ điểm trên mặt phẳng theo $x$ tăng dần, cùng $x$ thì theo $y$ tăng dần. Để thấy rõ từng phép so sánh pair, khung chạy tay dùng sắp xếp chèn: lấy lần lượt từng phần tử, dịch các phần tử lớn hơn nó sang phải (giống thao tác chèn ở bài 6) rồi đặt nó vào chỗ trống. Trong thực tế em chỉ cần viết sort(a, a + n); là xong:
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[1005];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i].first >> a[i].second;
// sort(a, a + n); cho kết quả y hệt đoạn dưới
for(int i = 1; i < n; i++){
pair<int, int> x = a[i];
int j = i - 1;
while(j >= 0 && a[j] > x){
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
for(int i = 0; i < n; i++)
cout << a[i].first << " " << a[i].second << "\n";
return 0;
}n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort() # tuple cũng so sánh theo kiểu từ điển như pair
for x, y in a:
print(x, y)Mô phỏng trực quan. So sánh hai pair thì so first trước, first bằng nhau mới so second; đọc thì hiểu nhưng tự làm tay lại hay rối. Em bấm Tiếp để xem sắp xếp chèn chạy trên mảng pair, mỗi lần so sánh đều ghi rõ máy đã nhìn vào first hay second.
Phần 3Hàm sort và hàm so sánh cmp
Hàm sort(a, a + n) trong <algorithm> sắp xếp tăng dần với độ phức tạp $O(n \log n)$, nhanh hơn hẳn sắp xếp chọn hay nổi bọt $O(n^2)$ ở bài 6: $n = 10^6$ chỉ mất khoảng 0,1 giây. Với vector viết sort(v.begin(), v.end()). Muốn sắp xếp giảm dần hoặc theo luật riêng, ta truyền thêm tham số thứ ba là một hàm so sánh:
Ví dụ bảng điểm: điểm cao đứng trước, bằng điểm thì tên đứng trước theo thứ tự từ điển. Python không dùng hàm cmp mà dùng key: một hàm biến mỗi phần tử thành “khóa”, Python sắp xếp tăng dần theo khóa. Muốn điểm giảm dần thì lấy khóa là -diem.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
struct HS { string ten; int diem; };
HS a[1005];
bool cmp(HS x, HS y){
if(x.diem != y.diem)
return x.diem > y.diem;
return x.ten < y.ten;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i].ten >> a[i].diem;
// sort(a, a + n, cmp); cho kết quả y hệt đoạn dưới
for(int i = 1; i < n; i++){
HS x = a[i];
int j = i - 1;
while(j >= 0 && cmp(x, a[j])){
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
for(int i = 0; i < n; i++)
cout << a[i].ten << " " << a[i].diem << "\n";
return 0;
}n = int(input())
a = []
for _ in range(n):
ten, diem = input().split()
a.append((ten, int(diem)))
a.sort(key=lambda h: (-h[1], h[0])) # điểm giảm dần (dấu trừ), rồi tên tăng dần
for ten, diem in a:
print(ten, diem)return x.diem >= y.diem; thì với hai bạn bằng điểm, cmp(x, y) và cmp(y, x) đều trả về true: “x đứng trước y” và “y đứng trước x” cùng lúc, vô lý! Hàm sort của C++ có thể chạy sai, thậm chí truy cập ngoài mảng và bị RTE. Quy tắc: cmp(x, x) luôn phải trả về false. Ngoài ra nên truyền tham số dạng const HS &x để khỏi sao chép struct mỗi lần so sánh, chạy nhanh hơn.sort(a, a + n, greater<int>()); sắp xếp giảm dần. sort(v.begin(), v.end()); sắp xếp vector. stable_sort giữ nguyên thứ tự ban đầu của các phần tử “bằng nhau”. Python: a.sort(reverse=True) giảm dần; sorted(a, key=len) theo độ dài; key=lambda t: (t[1], -t[0]) theo nhiều tiêu chí (mỗi tiêu chí giảm dần thì thêm dấu trừ nếu là số).Thử ngay: mô phỏng dưới đây cho em tự nhập danh sách và chọn tối đa 3 tiêu chí theo thứ tự ưu tiên, máy sẽ sắp xếp chèn từng bước và giải thích mỗi phép so sánh dựa trên tiêu chí nào.
Phần 4Hai ứng dụng: sắp xếp kèm chỉ số và xếp hạng có đồng hạng
Sắp xếp nhưng vẫn nhớ vị trí ban đầu. Nhiều đề hỏi “in ra chỉ số của các phần tử theo thứ tự tăng dần”. Sau khi sắp xếp, các số đã bị xáo trộn nên ta mất dấu chúng ở đâu. Mẹo: lưu mỗi phần tử dưới dạng pair(giá trị, chỉ số) rồi sắp xếp mảng pair. Nhờ cách so sánh pair, các giá trị bằng nhau tự xếp theo chỉ số tăng dần.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
pair<int, int> p[100005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> p[i].first; // giá trị
p[i].second = i; // chỉ số ban đầu (đánh số từ 1)
}
sort(p + 1, p + n + 1);
for(int i = 1; i <= n; i++) cout << p[i].second << " ";
return 0;
}n = int(input())
a = list(map(int, input().split()))
idx = sorted(range(1, n + 1), key=lambda i: (a[i - 1], i))
print(*idx)Xếp hạng có đồng hạng. Trong thi đấu, các bạn bằng điểm nhau thì đồng hạng, và người tiếp theo bị “nhảy hạng”: điểm 10, 9, 9, 7 thì xếp hạng 1, 2, 2, 4. Sau khi sắp xếp giảm dần, hạng của người thứ $i$ (đếm từ 1) là: nếu bằng điểm người ngay trước thì cùng hạng người đó, ngược lại hạng chính là $i$.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int d[1005], hang[1005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> d[i];
sort(d + 1, d + n + 1, greater<int>());
for(int i = 1; i <= n; i++){
if(i > 1 && d[i] == d[i - 1])
hang[i] = hang[i - 1];
else
hang[i] = i;
}
for(int i = 1; i <= n; i++)
cout << d[i] << " " << hang[i] << "\n";
return 0;
}n = int(input())
d = sorted(map(int, input().split()), reverse=True)
hang = [0] * n
for i in range(n):
hang[i] = hang[i - 1] if i > 0 and d[i] == d[i - 1] else i + 1
for x, h in zip(d, hang):
print(x, h)Mô phỏng trực quan. Xếp hạng có đồng hạng gồm ba bước nối tiếp nhau, dễ lạc ở bước "trả hạng về đúng người". Em nhập điểm của cả lớp rồi bấm Tiếp để xem từng bước; thử cho nhiều bạn bằng điểm để thấy hạng "nhảy cóc" như 1, 2, 2, 4.
Bài tậpLuyện struct, pair và sắp xếp
Giới hạn chung: $n \le 10^5$, nên mọi bài đều cần sắp xếp bằng sort $O(n \log n)$ thay vì tự viết sắp xếp $O(n^2)$. Tên là một từ, không có dấu cách.
Cho $n$ học sinh, mỗi dòng gồm tên và điểm (số nguyên). In tên học sinh có điểm cao nhất; nếu nhiều bạn bằng điểm, in bạn có tên nhỏ nhất theo thứ tự từ điển.
4
Minh 9
An 9
Tuan 8
Bao 7An💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
string best = "";
int bd = -1;
for(int i = 0; i < n; i++){
string t; int d;
cin >> t >> d;
if(d > bd || (d == bd && t < best)){
bd = d; best = t;
}
}
cout << best;
return 0;
}n = int(input())
a = [input().split() for _ in range(n)]
best = min(a, key=lambda t: (-int(t[1]), t[0]))
print(best[0])Cho $n$ điểm $(x, y)$ nguyên. In các điểm theo $x$ tăng dần, cùng $x$ thì $y$ giảm dần.
4
2 1
1 5
2 7
1 31 5
1 3
2 7
2 1💡 Gợi ý
x.first != y.first thì return x.first < y.first;, ngược lại return x.second > y.second;. Mẹo khác: lưu $(x, -y)$ rồi sort bình thường. Python: key=lambda p: (p[0], -p[1]).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[100005];
bool cmp(const pair<int, int> &p, const pair<int, int> &q){
if(p.first != q.first) return p.first < q.first;
return p.second > q.second;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
sort(a, a + n, cmp);
for(int i = 0; i < n; i++) cout << a[i].first << " " << a[i].second << "\n";
return 0;
}n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda p: (p[0], -p[1]))
for x, y in a:
print(x, y)Cho $n$ học sinh gồm tên và điểm. In tên theo điểm giảm dần, bằng điểm thì tên tăng dần theo thứ tự từ điển, mỗi tên một dòng.
5
Nam 8
An 9
Lan 8
Bao 9
Hoa 7An
Bao
Lan
Nam
Hoa💡 Gợi ý
string ten; int diem;, gọi sort(a, a + n, cmp).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
struct HS { string ten; int diem; };
HS a[100005];
bool cmp(const HS &x, const HS &y){
if(x.diem != y.diem) return x.diem > y.diem;
return x.ten < y.ten;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i].ten >> a[i].diem;
sort(a, a + n, cmp);
for(int i = 0; i < n; i++) cout << a[i].ten << "\n";
return 0;
}n = int(input())
a = []
for _ in range(n):
t, d = input().split()
a.append((t, int(d)))
a.sort(key=lambda h: (-h[1], h[0]))
print('\n'.join(t for t, d in a))Cho điểm của $n$ học sinh theo thứ tự nhập. In ra hạng của từng bạn theo đúng thứ tự nhập ban đầu (điểm cao hạng nhỏ, bằng điểm đồng hạng, người sau bị nhảy hạng).
5
8 9 8 7 93 1 3 5 1💡 Gợi ý
pair(điểm, chỉ số), sắp xếp giảm dần theo điểm, tính hạng như khung chạy tay rồi ghi vào kq[chỉ số ban đầu]. Cuối cùng in mảng kq theo thứ tự 1..n.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
pair<int, int> p[100005];
int kq[100005];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){ cin >> p[i].first; p[i].second = i; }
sort(p, p + n, [](const pair<int,int> &a, const pair<int,int> &b){ return a.first > b.first; });
int hang = 0;
for(int i = 0; i < n; i++){
if(i == 0 || p[i].first != p[i - 1].first) hang = i + 1;
kq[p[i].second] = hang;
}
for(int i = 0; i < n; i++) cout << kq[i] << " ";
return 0;
}n = int(input())
a = list(map(int, input().split()))
s = sorted(a, reverse=True)
hang = {}
for i, x in enumerate(s):
if x not in hang:
hang[x] = i + 1
print(*[hang[x] for x in a])Cho dãy $n$ số. In ra các chỉ số (đánh số từ 1) theo thứ tự giá trị tăng dần; giá trị bằng nhau thì chỉ số nhỏ in trước.
5
30 10 20 10 502 4 3 1 5💡 Gợi ý
pair(giá trị, chỉ số) ở phần 4, sort mặc định là đủ vì pair tự so second khi first bằng nhau.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
pair<int, int> p[100005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){ cin >> p[i].first; p[i].second = i; }
sort(p + 1, p + n + 1);
for(int i = 1; i <= n; i++) cout << p[i].second << " ";
return 0;
}n = int(input())
a = list(map(int, input().split()))
print(*sorted(range(1, n + 1), key=lambda i: (a[i - 1], i)))Cho $n$ số nguyên dương ($\le 10^9$). Sắp xếp theo tổng chữ số tăng dần; cùng tổng chữ số thì số nhỏ hơn đứng trước.
5
91 19 100 23 5100 5 23 19 91💡 Gợi ý
pair(tổng chữ số, số) rồi sort. Đừng tính tổng chữ số bên trong hàm cmp: cmp được gọi khoảng $n \log n$ lần, tính đi tính lại sẽ chậm.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
pair<int, int> p[100005];
int tcs(int x){
int s = 0;
while(x > 0){ s += x % 10; x /= 10; }
return s;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
int x; cin >> x;
p[i] = {tcs(x), x};
}
sort(p, p + n);
for(int i = 0; i < n; i++) cout << p[i].second << " ";
return 0;
}n = int(input())
a = list(map(int, input().split()))
a.sort(key=lambda x: (sum(map(int, str(x))), x))
print(*a)Có $n$ hoạt động, hoạt động thứ $i$ bắt đầu lúc $s_i$ và kết thúc lúc $e_i$. Một người chỉ tham gia được một hoạt động tại mỗi thời điểm (hoạt động sau được bắt đầu đúng lúc hoạt động trước kết thúc). Hỏi tham gia được nhiều nhất bao nhiêu hoạt động?
5
1 3
2 5
4 6
6 8
5 73💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[100005]; // lưu (kết thúc, bắt đầu) để sort theo kết thúc
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
int s, e; cin >> s >> e;
a[i] = {e, s};
}
sort(a, a + n);
int dem = 0, ketthuc = INT_MIN;
for(int i = 0; i < n; i++){
if(a[i].second >= ketthuc){
dem++;
ketthuc = a[i].first;
}
}
cout << dem;
return 0;
}n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda t: t[1])
dem, kt = 0, float('-inf')
for s, e in a:
if s >= kt:
dem += 1
kt = e
print(dem)Cho $n$ từ. Sắp xếp theo độ dài tăng dần, cùng độ dài thì theo thứ tự từ điển. In mỗi từ một dòng.
5
banana
apple
kiwi
fig
cherryfig
kiwi
apple
banana
cherry💡 Gợi ý
if(x.size() != y.size()) return x.size() < y.size(); return x < y;. Python: key=lambda w: (len(w), w).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
string a[100005];
bool cmp(const string &x, const string &y){
if(x.size() != y.size()) return x.size() < y.size();
return x < y;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n, cmp);
for(int i = 0; i < n; i++) cout << a[i] << "\n";
return 0;
}n = int(input())
a = [input().strip() for _ in range(n)]
a.sort(key=lambda w: (len(w), w))
print('\n'.join(a))
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét