Arrays

Mảng là dãy ô đánh số từ 0

Khai báo int a[5]; tạo năm ô kiểu int dưới cùng một tên a. Mỗi ô được gọi bằng tên mảng và chỉ số (index) đặt trong ngoặc vuông: a[0], a[1], a[2], a[3], a[4]. Một ô dùng như biến thường: có thể gán, cộng, in. Số trong ngoặc lúc khai báo là số ô; số trong ngoặc lúc dùng là thứ tự của ô, và ô đầu tiên có thứ tự 0.

Ta cho giá trị ban đầu ngay khi khai báo, trong cặp ngoặc nhọn; viết thiếu thì các ô còn lại bằng 0, nên int a[5] = {3, 1}; cho 3 1 0 0 0. Sau dấu } này phải có dấu chấm phẩy.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a[5] = {3, 1, 4, 1, 5};
    cout << a[0] << ' ' << a[4] << '\n';
    a[2] = 10;
    cout << a[2] + a[3] << '\n';
}

Output3 5
11

Mảng năm ô có chỉ số từ 0 đến 4, không có a[5]. Tổng quát, mảng $n$ ô chỉ có các chỉ số $0, 1, \dots, n - 1$. Viết a[5] thì g++ vẫn biên dịch, vì C++ không kiểm tra chỉ số. Khi chạy, chương trình chạm vào vùng nhớ không thuộc mảng: có thể đọc ra số rác, có thể ghi đè lên một biến khác, có thể dừng với lỗi chạy (runtime error). Đây là lỗi chỉ số ngoài mảng, lỗi hay gặp nhất của bài này.

Đề bài thường đếm vị trí từ 1: “phần tử thứ $k$” là $a_k$. Trong C++ phần tử ấy nằm ở chỉ số $k - 1$.

Có hai cách để chỉ số khớp với đề. Cách một là như trên: đọc vào a[0..n-1] rồi đổi vị trí $k$ thành chỉ số $k - 1$. Cách hai là bỏ phí ô 0 và đọc vào a[1..n], nên vị trí $k$ nằm đúng ở a[k]; mảng khi đó cần ít nhất $n + 1$ ô, và vòng duyệt chạy i từ 1 đến n. Cả hai đều đúng, chỉ không được trộn lẫn trong một chương trình. Bài này dùng cách một; từ chương 0, như tổng tiền tố (bài 02), ta dùng cách hai.

Số ô của mảng là một hằng số viết ngay lúc khai báo. Đề cho $n \le 100$ thì khai báo dư vài ô, ví dụ int a[105];, và chỉ dùng $n$ ô đầu. Đừng viết int a[n] với $n$ vừa đọc vào: g++ chấp nhận, nhưng đó không phải C++ chuẩn; khi số ô chỉ biết lúc chạy, ta dùng vector ở mục cuối. Hai mảng cũng không gán cho nhau bằng b = a;; muốn sao chép thì chép từng ô bằng vòng for.

Chỗ khai báo cũng quan trọng. Mảng đặt bên ngoài mọi hàm (mảng toàn cục) có mọi ô bằng 0 lúc chương trình bắt đầu. Mảng đặt trong main mà chưa gán thì chứa số rác. Mảng lớn càng phải để toàn cục, vì mảng trong hàm nằm ở vùng ngăn xếp (stack) chỉ rộng vài megabyte, dễ tràn khi mảng có hàng triệu phần tử. Từ đây mảng luôn khai báo toàn cục.

Ví dụPhần tử thứ k

Đề. Cho mảng $n$ số nguyên ($n \le 100$), vị trí đánh số từ 1, và một vị trí $k$ ($1 \le k \le n$). In phần tử ở vị trí $k$.

Lời giải. Đọc $n$ số vào a[0..n-1] bằng một vòng for, rồi mới đọc $k$: thứ tự đọc là thứ tự trong đề, và $k$ nằm ở dòng cuối. Vị trí $k$ của đề nằm ở chỉ số $k - 1$, nên in a[k - 1]. In a[k] thì với test ví dụ máy in 0 thay vì -1, và với $k = n$ thì đọc ra ngoài phần đã dùng.

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

int a[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> k;
    cout << a[k - 1] << '\n';
}

Input4
3 -1 0 7
2

Output-1

Đọc, in và cộng dồn

Việc nào với mảng cũng bắt đầu giống nhau: đọc $n$, rồi đọc $n$ số vào a[0], ..., a[n - 1] bằng một vòng for. Trong vòng for (int i = 0; i < n; i++), biến i nhận lần lượt $0, 1, \dots, n - 1$, đúng các chỉ số hợp lệ. Điều kiện là i < n, không phải i <= n.

Chương trình dưới đọc mảng, in lại, rồi tính tổng và đếm số phần tử chẵn.

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

int a[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int sum = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (a[i] % 2 == 0) cnt++;
    }

    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << '\n' << sum << '\n' << cnt << '\n';
}

Input5
2 -3 0 4 7

Output2 -3 0 4 7
10
3

Ba chỗ hay sai nằm ngay trong đoạn ngắn này. Biến cộng dồn phải được gán giá trị đầu: int sum; trong main chứa số rác, và sum += a[i] cộng vào số rác ấy. Kiểm số lẻ thì viết a[i] % 2 != 0, không viết == 1, vì -3 % 2 bằng $-1$. Và kiểu của tổng: ở đây $|a_i| \le 1000$, $n \le 100$ nên tổng không vượt $10^5$, int đủ; khi đề cho $2 \cdot 10^5$ số cỡ $10^9$, tổng lên tới $2 \cdot 10^{14}$ và phải dùng long long.

Ví dụNhững phần tử vượt trung bình

Đề. Cho mảng $n \le 200$ số nguyên trong $[-1000, 1000]$, vị trí đánh số từ 1. In số vị trí có giá trị lớn hơn trung bình cộng của cả mảng, rồi in các vị trí đó theo thứ tự tăng dần; không có thì in dòng trống.

Lời giải. Trung bình cộng chỉ biết sau khi cộng hết mảng, nên phải lưu mảng và duyệt hai lượt: lượt một tính tổng $S$, lượt hai so từng phần tử. Các vị trí chọn được ghi vào mảng thứ hai p cùng biến đếm m; p[m++] = i + 1 ghi vào ô m rồi mới tăng m.

Điều kiện $a_i > S / n$ tương đương $a_i \cdot n > S$, vì $n > 0$; dạng nhân giữ mọi thứ là số nguyên. Viết a[i] > sum / n thì phép chia nguyên cắt phần lẻ về phía 0, và với tổng âm sẽ sai: mảng $(-3, -4)$ có trung bình $-3{,}5$ nên $-3$ phải được chọn, nhưng -7 / 2 bằng $-3$ và -3 > -3 sai. $a_i \cdot n$ không quá $2 \cdot 10^5$, int đủ. Với ví dụ, $S = 10$, $n = 5$, ta giữ các $a_i > 2$: vị trí 2, 4, 5.

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

int a[205], p[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] * n > sum) p[m++] = i + 1;
    }
    cout << m << '\n';
    for (int i = 0; i < m; i++) cout << p[i] << ' ';
    cout << '\n';
}

Input5
-1 4 0 4 3

Output3
2 4 5

Lớn nhất, nhỏ nhất và vị trí

Để tìm số lớn nhất ta giữ một biến mx ghi số lớn nhất đã thấy cho tới giờ, rồi so từng phần tử: lớn hơn thì thay. Giá trị đầu an toàn nhất là phần tử đầu tiên a[0]: sau khi xem một phần tử, số lớn nhất đã thấy chính là nó. Đừng khởi tạo bằng 0: dãy $-5, -2, -8$ không có số nào lớn hơn 0, nên mx ở lại 0, một số không thuộc dãy. Từ đó vòng lặp chạy từ i = 1, và sau mỗi lượt, mx là số lớn nhất của a[0..i].

Với số nhỏ nhất làm tương tự, đổi dấu so sánh. Để biết vị trí, ta giữ chỉ số thay vì giữ giá trị: biến p là chỉ số của số nhỏ nhất đã thấy, và a[p] là chính số đó.

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

int a[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int mx = a[0], p = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > mx) mx = a[i];
        if (a[i] < a[p]) p = i;
    }
    cout << mx << '\n' << p + 1 << '\n';
}

Input4
3 -2 5 -2

Output5
2

Chạy tay trên 3 -2 5 -2: mx đi qua $3, 3, 5, 5$ và p đi qua $0, 1, 1, 1$. Ở bước cuối a[3] = -2 không nhỏ hơn a[1] = -2 nên vị trí vẫn là chỉ số 1, tức vị trí 2 trong đề (in p + 1). Dấu < chặt giữ vị trí đầu tiên của số nhỏ nhất; viết <= thì ta nhận vị trí cuối cùng. Mỗi phần tử được xem đúng một lần, nên cả lượt duyệt chỉ tốn khoảng $n$ bước.

Ví dụĐếm cực đại

Đề. Cho mảng $n$ số nguyên ($n \le 100$). In số phần tử bằng giá trị lớn nhất của mảng.

Lời giải. Hai lượt là cách thẳng nhất: lượt một tìm mx, lượt hai đếm các a[i] == mx. Làm được trong một lượt nếu giữ cả mx lẫn số lần cnt nó đã xuất hiện: gặp số lớn hơn mx thì người dẫn đầu đổi, mx = a[i] và cnt quay về 1; gặp số bằng mx thì cnt tăng. Với 4 7 7 2 7: (mx, cnt) đi qua $(4, 1), (7, 1), (7, 2), (7, 2), (7, 3)$. Đặt lại cnt = 1 khi đổi mx là chỗ hay quên: thiếu nó, những lần gặp số 4 cũ vẫn bị cộng vào.

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

int a[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int mx = a[0], cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] > mx) {
            mx = a[i];
            cnt = 1;
        } else if (a[i] == mx) {
            cnt++;
        }
    }
    cout << cnt << '\n';
}

Input5
4 7 7 2 7

Output3

Tìm kiếm và kiểm tra tính chất

Mọi phần tử đều thỏa. Một tính chất kiểu “mảng tăng nghiêm ngặt” cần mọi cặp kề nhau thỏa. Ta dùng một cờ (flag), biến bool đặt true từ đầu, và chỉ cần gặp một phản ví dụ là đặt false. Mảng tăng nghiêm ngặt khi a[i] > a[i - 1] với mọi i từ 1 đến n - 1, nên phản ví dụ là một i có a[i] <= a[i - 1]. Mảng một phần tử không có cặp nào để vi phạm nên cờ ở lại true, khớp với định nghĩa. Làm ngược lại, đặt false từ đầu rồi bật true mỗi lần thấy một cặp tốt, là kiểm “tồn tại một cặp tốt”, không phải “mọi cặp đều tốt”.

Đối xứng. Mảng đối xứng khi đọc xuôi và đọc ngược cho cùng dãy, tức a[i] == a[n - 1 - i] với mọi $i$. Mỗi cặp $(i, n - 1 - i)$ chỉ cần kiểm một lần, nên $i$ chạy từ 0 tới n / 2 - 1; phần tử chính giữa khi $n$ lẻ tự bằng chính nó. n / 2 là chia nguyên: với $n = 5$ nó bằng 2, nên $i$ chỉ nhận 0 và 1.

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

int a[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    bool inc = true;
    for (int i = 1; i < n; i++) {
        if (a[i] <= a[i - 1]) inc = false;
    }
    bool sym = true;
    for (int i = 0; i < n / 2; i++) {
        if (a[i] != a[n - 1 - i]) sym = false;
    }
    cout << (inc ? "YES" : "NO") << '\n';
    cout << (sym ? "YES" : "NO") << '\n';
}

Input5
1 3 3 3 1

OutputNO
YES

Tìm vị trí đầu tiên của $x$. Duyệt từ đầu, gặp phần tử bằng $x$ thì ghi vị trí. Muốn lần gặp đầu tiên thì phải dừng ngay bằng break; thiếu break, vòng lặp chạy tiếp và ghi đè bằng lần gặp cuối. Khi không gặp, kết quả phải nói được điều đó: đặt pos = -1 trước vòng lặp, vì $-1$ không bao giờ là một vị trí thật. Và phép so sánh luôn là ==: if (a[i] = x) gán $x$ vào a[i], phá dữ liệu, và đúng với mọi $x \ne 0$.

Ví dụTìm lần đầu

Đề. Cho mảng $n$ số nguyên ($n \le 100$, $|a_i| \le 1000$) và số $x$ ($|x| \le 1001$), vị trí đánh số từ 1. In vị trí đầu tiên có giá trị bằng $x$, không có thì in $-1$.

Lời giải. Đặt pos = -1, duyệt i từ 0; gặp a[i] == x thì ghi pos = i + 1 (đổi chỉ số thành vị trí) và break. Test ví dụ có hai số 2, ở vị trí 2 và 5: thiếu break thì máy in 5. Đề cố tình cho $x$ tới 1001, ngoài miền giá trị của mảng, để có test không tìm thấy; khi đó vòng chạy hết và pos giữ $-1$.

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

int a[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;
    int pos = -1;
    for (int i = 0; i < n; i++) {
        if (a[i] == x) {
            pos = i + 1;
            break;
        }
    }
    cout << pos << '\n';
}

Input5
4 2 4 7 2
2

Output2

Hoán đổi và đảo mảng

Hoán đổi (swap) hai ô nghĩa là ô này nhận giá trị của ô kia và ngược lại. Viết thẳng hai phép gán là sai. Với a[0] = 3, a[1] = 8, các dòng a[0] = a[1]; rồi a[1] = a[0]; làm a[0] thành 8 và số 3 mất hẳn, dòng sau chỉ chép lại số 8 đó. Phải cất giá trị cũ vào một biến tạm trước khi ghi đè:

int t = a[i];
a[i] = a[j];
a[j] = t;

Ba dòng này đúng cả khi $i = j$. C++ có sẵn swap(a[i], a[j]) làm đúng việc ấy, và từ đây ta dùng nó.

Đảo mảng là đưa mảng về thứ tự ngược. Ô đầu đổi chỗ với ô cuối, ô thứ hai đổi chỗ với ô thứ hai tính từ cuối, và cứ thế vào giữa: ô i đổi với ô n - 1 - i. Chỉ cần đổi các cặp với i < n / 2. Cho i chạy hết $n$ ô thì mỗi cặp bị đổi hai lần và mảng trở về như cũ.

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

int a[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n / 2; i++) swap(a[i], a[n - 1 - i]);
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << '\n';
}

Input6
4 8 1 9 6 2

Output2 6 9 1 8 4

Muốn viết một hàm nhận mảng qua tham số, khai báo void f(int a[], int n). Khác với tham số int ở bài B4, mảng không bị chép: hàm làm việc trên chính mảng của nơi gọi, nên sửa trong hàm là sửa thật. Hàm cũng không biết mảng có bao nhiêu phần tử, nên phải truyền n kèm theo. Với mảng toàn cục thì khỏi truyền gì cả.

Ví dụĐảo một đoạn

Đề. Cho mảng $a_1, \dots, a_n$ ($n \le 200$) và hai vị trí $l \le r$. Đảo thứ tự các phần tử từ vị trí $l$ đến vị trí $r$, gồm cả hai đầu; ngoài đoạn giữ nguyên. In mảng sau thao tác.

Lời giải. Giống đảo cả mảng, chỉ khác hai đầu: giữ hai chỉ số i ở đầu đoạn, j ở cuối đoạn, đổi chỗ a[i] với a[j] rồi cho chúng tiến vào nhau, tới khi gặp hoặc vượt nhau. Vị trí $l, r$ của đề là chỉ số $l - 1, r - 1$. Với đoạn lẻ phần tử, i và j gặp nhau ở giữa và vòng dừng, phần tử giữa đứng yên; với $l = r$ vòng không chạy lượt nào.

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

int a[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, l, r;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> l >> r;
    int i = l - 1, j = r - 1;
    while (i < j) {
        swap(a[i], a[j]);
        i++;
        j--;
    }
    for (int k = 0; k < n; k++) cout << a[k] << ' ';
    cout << '\n';
}

Input5
1 2 3 4 5
2 4

Output1 4 3 2 5

Chèn và xóa

Mảng không tự dãn ra hay co lại. Chèn $x$ vào vị trí $k$ nghĩa là các phần tử từ vị trí $k$ trở đi lùi sang phải một ô để nhường chỗ. Xóa phần tử ở vị trí $k$ nghĩa là các phần tử phía sau nó tiến sang trái một ô để lấp chỗ trống. Ta theo dõi số phần tử đang dùng bằng biến n.

Thứ tự dịch quyết định đúng sai, và có một cách nhớ: dịch sang phía nào thì bắt đầu từ phía đó. Khi chèn ta dịch sang phải, nên bắt đầu từ ô cuối và đi ngược về $k$; mỗi giá trị đã được chép đi trước khi ô của nó bị ghi đè. Khi xóa ta dịch sang trái, nên bắt đầu từ ô bị xóa (nhận giá trị của ô ngay sau nó) rồi đi dần về cuối. Hình dưới là chèn 9 vào vị trí 2 của mảng $(2, 4, 6)$.

Chương trình dưới chèn $x$ vào vị trí $k$ (đếm từ 1, $1 \le k \le n + 1$), in mảng, rồi xóa phần tử ở vị trí $k'$ và in lại.

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

int a[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k, x;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> k >> x;
    for (int i = n; i > k - 1; i--) a[i] = a[i - 1];
    a[k - 1] = x;
    n++;
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << '\n';

    cin >> k;
    for (int i = k - 1; i < n - 1; i++) a[i] = a[i + 1];
    n--;
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << '\n';
}

Input3
2 4 6
2 9
1

Output2 9 4 6
9 4 6

Mỗi lần chèn hay xóa phải dịch tới $n$ ô. Với $n \le 200$ chuyện đó không đáng kể, nhưng $10^5$ lần chèn vào mảng cỡ $10^5$ phần tử là khoảng $10^{10}$ lần dịch, quá chậm; đề kiểu ấy cần cách khác. Khi chèn, mảng phải còn chỗ cho phần tử thứ $n + 1$, vì ta ghi vào a[n]. Khi xóa, ô cuối vẫn giữ giá trị cũ nhưng nằm ngoài $n$ ô đang dùng, nên không ai đọc tới nó.

Ví dụChèn vào dãy không giảm

Đề. Cho mảng không giảm $a_1 \le a_2 \le \dots \le a_n$ ($n \le 200$) và số $x$. Chèn $x$ sau tất cả phần tử không lớn hơn $x$, dịch phần phía sau sang phải. In vị trí vừa chèn, rồi mảng mới.

Lời giải. Vì mảng không giảm, các phần tử không lớn hơn $x$ đứng thành một khúc ở đầu. Đếm khúc đó bằng k: tăng k chừng nào k < n và a[k] <= x. Vế k < n đứng trước là lính gác: khi mọi phần tử đều $\le x$, k chạm $n$ thì vòng dừng mà không đọc a[n]. Chỉ số k chính là chỗ đặt $x$, tức vị trí $k + 1$. Rồi chèn như ở trên: dịch từ cuối về k, đặt a[k] = x. Với ví dụ, ba số $-1, 2, 2$ không lớn hơn 2, nên $k = 3$ và $x$ vào vị trí 4.

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

int a[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;
    int k = 0;
    while (k < n && a[k] <= x) k++;
    for (int i = n; i > k; i--) a[i] = a[i - 1];
    a[k] = x;
    n++;
    cout << k + 1 << '\n';
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << '\n';
}

Input5
-1 2 2 5 9
2

Output4
-1 2 2 2 5 9

Mảng đếm

Giả sử cần biết mỗi giá trị xuất hiện bao nhiêu lần, các giá trị nằm trong khoảng $[-1000, 1000]$. Mỗi giá trị một vòng duyệt riêng thì phải làm $2001$ lượt, mỗi lượt $n$ phép so. Có cách gọn hơn: lấy chính giá trị làm chỉ số. Mảng cnt giữ cnt[v] là số lần giá trị $v$ đã xuất hiện; đọc số nào thì tăng ô của số đó lên 1. Một lượt đọc là xong, và đó là mảng đếm (counting array).

Chỉ số không được âm, mà giá trị có thể âm. Ta dịch mọi giá trị lên một lượng cố định: giá trị $v$ ghi vào ô v + 1000. Giá trị $-1000$ vào ô 0, giá trị $1000$ vào ô 2000, và mảng cần 2001 ô. Khi tra cứu cũng phải cộng đúng lượng ấy.

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

int cnt[2005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        cnt[v + 1000]++;
    }
    for (int v = -1000; v <= 1000; v++) {
        if (cnt[v + 1000] > 0) cout << v << ": " << cnt[v + 1000] << '\n';
    }
}

Input6
4 -2 4 7 -2 4

Output-2: 2
4: 3
7: 1

Chương trình không cần giữ cả dãy: mỗi số đọc xong là đếm luôn. Cẩn thận khi giá trị cần tra có thể nằm ngoài khoảng đã dựng mảng: đề cho $x$ tới $1001$ thì cnt[x + 1000] là ô 2001, vẫn trong 2005 ô đã khai báo và bằng 0, nhưng $x = 1006$ thì đã ra ngoài. Nếu một file chứa nhiều bộ dữ liệu thì cnt phải được đưa về 0 trước mỗi bộ, vì mảng toàn cục chỉ bằng 0 lúc chương trình bắt đầu; memset(cnt, 0, sizeof(cnt)); làm việc đó.

Mảng đếm chỉ hợp khi miền giá trị nhỏ. Một mảng int có $10^6$ ô chiếm 4 MB, $10^7$ ô chiếm 40 MB, nên cỡ vài triệu ô là mức hợp lý so với giới hạn bộ nhớ thường gặp (256 MB). Với giá trị tới $10^9$ phải đổi cách: sắp xếp (bài 03) hoặc map (bài 09).

Ví dụGhép thẻ

Đề. An có $n$ thẻ, Bình có $m$ thẻ ($n, m \le 100$), mỗi thẻ ghi một số nguyên trong $[-1000, 1000]$. Một thẻ của An ghép với một thẻ của Bình nếu cùng số, mỗi thẻ dùng nhiều nhất một lần. In số cặp lớn nhất.

Lời giải. Hai thẻ chỉ ghép được khi cùng số, nên các số khác nhau không ảnh hưởng nhau và ta xét riêng từng số. Nếu An có 2 thẻ số 7 còn Bình có 3 thẻ số 7 thì ghép được nhiều nhất 2 cặp số 7, vì mỗi cặp cần một thẻ của An; cứ ghép tới khi một bên hết thẻ là đạt con số đó. Vậy mỗi số cho số cặp bằng số nhỏ hơn trong hai số lượng thẻ, và đáp án là tổng các số đó, tính bằng hai mảng đếm. Với ví dụ, số 2 cho $\min(2, 1) = 1$ cặp, số 7 cho $\min(1, 2) = 1$ cặp, số 9 chỉ An có: tổng 2.

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

int ca[2005], cb[2005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        ca[v + 1000]++;
    }
    for (int i = 0; i < m; i++) {
        int v;
        cin >> v;
        cb[v + 1000]++;
    }
    int ans = 0;
    for (int v = 0; v <= 2000; v++) ans += min(ca[v], cb[v]);
    cout << ans << '\n';
}

Input4 3
2 2 7 9
2 7 7

Output2

Vector và mảng hai chiều

Mảng thường có hai điểm bất tiện: số ô phải là hằng số viết sẵn, và không thêm ô được. vector bỏ cả hai. vector<int> a(n); tạo $n$ ô bằng 0 (với $n$ đọc vào cũng được), vector<int> a(n, -1); tạo $n$ ô bằng $-1$, còn vector<int> a; chưa có ô nào. Ô vẫn gọi bằng a[i] với chỉ số từ 0, và vẫn không có kiểm tra chỉ số ngoài mảng. Có thêm hai thao tác: a.size() cho số ô hiện có, a.push_back(x) thêm một ô chứa $x$ vào cuối. Số ô đặt trong ngoặc tròn; viết vector<int> a{n}; với ngoặc nhọn lại tạo mảng một ô chứa giá trị $n$.

a.size() có kiểu không dấu, nên với vector rỗng a.size() - 1 không bằng $-1$ mà là một số cực lớn; ép kiểu (int)a.size() khi so sánh hoặc trừ. Truyền vector vào hàm là truyền bản sao như int ở bài B4, nên hàm cần sửa thì khai báo tham số vector<int> &a.

Bảng gồm $R$ hàng và $C$ cột là mảng của các mảng. Ô ở hàng $i$, cột $j$ là g[i][j]: chỉ số đầu là hàng, chỉ số sau là cột, cả hai đếm từ 0. Bảng khai báo toàn cục là int g[105][105];. Ta duyệt bảng bằng hai vòng for lồng nhau, vòng ngoài theo hàng, vòng trong theo cột. Chương trình dưới đọc một bảng rồi tính tổng từng hàng và tổng từng cột.

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

int g[105][105], row[105], col[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int R, C;
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> g[i][j];
            row[i] += g[i][j];
            col[j] += g[i][j];
        }
    }
    for (int i = 0; i < R; i++) cout << row[i] << ' ';
    cout << '\n';
    for (int j = 0; j < C; j++) cout << col[j] << ' ';
    cout << '\n';
}

Input3 4
1 -2 3 4
-5 0 2 -1
6 7 -8 9

Output6 -4 14
2 5 -3 12

Tổng của ba hàng và tổng của bốn cột cùng bằng 16, tổng cả bảng: một cách kiểm nhanh khi chạy tay. Lỗi hay gặp là lẫn $R$ với $C$: vòng theo i chạy tới $R$ (số hàng), vòng theo j chạy tới $C$ (số cột). Bảng vuông che lỗi này đi, còn bảng $3 \times 4$ như trên làm nó lộ ra.

Ví dụLọc theo giá trị

Đề. Cho mảng $n \le 200$ số nguyên và số $x$. Xóa mọi phần tử bằng $x$, giữ thứ tự các phần tử còn lại. In số phần tử còn lại, rồi các phần tử đó; mảng rỗng thì in dòng trống.

Lời giải. Xóa từng phần tử bằng cách dịch như mục trước thì mỗi lần phải dịch tới $n$ ô. Gọn hơn là dựng mảng kết quả từ đầu: duyệt mảng gốc, phần tử nào khác $x$ thì push_back vào b. Thứ tự giữ nguyên vì ta duyệt từ trái sang, và b.size() chính là số phần tử còn lại. Khi mọi phần tử đều bằng $x$, b rỗng, chương trình in 0 rồi một dòng trống, đúng như đề.

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

int a[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;
    vector<int> b;
    for (int i = 0; i < n; i++) {
        if (a[i] != x) b.push_back(a[i]);
    }
    cout << b.size() << '\n';
    for (int i = 0; i < (int)b.size(); i++) cout << b[i] << ' ';
    cout << '\n';
}

Input6
2 5 2 7 2 9
2

Output3
5 7 9