---
title
Sắp xếp - Lời giải
---

Sắp xếp - Lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Bài 1: [VDCoder - SUMFIVE - Tổng 5 phần tử](https://vinhdinhcoder.net/Problem/Details/4666)

#### Đề Bài

- Cho dãy số nguyên gồm $n$ phần tử $B_1, B_2, ..., B_n$ $(n ≤ 5000, |B_i| ≤ 10^9)$. Bạn được quyền chọn ra $5$ phần tử bất kỳ sao cho tổng của chúng lớn nhất có thể. Hỏi tổng lớn nhất mà bạn nhận được là bao nhiêu?

#### Input

- Dòng $1$ là số nguyên $n$
- Dòng $2$ là các phần tử trong dãy $B$.

#### Output

- In ra một số nguyên duy nhất là tổng thu được.

#### Sample Input

6
6 93 37 81 63 61

#### Sample Output

335

#### Giải thích

- Tổng thu được khi ta chọn $5$ số $93,37,81,63,61$ là: $93+37+81+63+61=335$

#### Lời giải

- Cách chọn tối ưu nhất là chọn $5$ phần tử lớn nhất mảng. Khi đó tổng của $5$ phần tử đó cũng là lớn nhất.
- Ta có thể dùng hàm `std::sort()` để sắp xếp mảng theo thứ tự **không tăng**. $5$ phần tử lớn nhất mảng là $5$ phần tử đầu tiên.
- **Lưu ý:** Vì mỗi phần tử có thể đạt đến $10^9$, tổng 5 phần tử có thể đạt đến $5\cdot10^9$ tràn giới hạn số của `int`, sau khi sắp xếp ta cần cộng từng số vào biến kiểu `long long` để tránh tràn số.
::: spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

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

    sort(a.begin(), a.end(), greater<int>());

    long long ans = 0;
    for(int i = 0; i < 5; ++i) ans += a[i]; 
    // Vì mỗi phần tử là 10^9, 5 phần tử có thể đạt đến 5*10^9, ta cần cộng từng phần tử vào 1 biến long long
    cout << ans;
}

:::

- Ngoài ra, ở bài viết [Sắp xếp](https://hackmd.io/BmAVjN6KQkWmwzPotONuew?view#1-S%E1%BA%AFp-x%E1%BA%BFp-n%E1%BB%95i-b%E1%BB%8Dt-Bubble-sort), tụi mình đã đề cập đến tính chất của thuật toán **Bubble sort** trong phần chứng minh là sẽ đưa phần tử lớn nhất ra cuối mảng, ta có thể áp dụng tính chất này vào bài tập bằng cách chạy $5$ lần lặp.

::: spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

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

    for (int t = 1; t <= 5; ++t)
    {
        for (int i = 0; i < n-1; ++i)
        {
            if(a[i] > a[i + 1]) swap(a[i], a[i + 1]);
        }
    }

    long long ans = 0;
    for(int i = n - 5; i < n; ++i) ans += a[i];
    cout << ans;
}

:::

- Cách đầu tiên có độ phức tạp là $O(n\cdot log{n})$ trong khi cách thứ hai có độ phức tạp là $O(5\cdot n) = O(n)$. Tuy nhiên, vì giới hạn $n$ trong bài tập khá nhỏ (chỉ có $5000$), cả hai cách làm nhìn chung là tương đương nhau.

# Bài 2: [CSES - Distinct Number](https://cses.fi/problemset/task/1621)
#### Đề Bài

- Bạn được cho một dãy số gồm $n$ số nguyên dương, nhiệm vụ của bạn là tính số giá trị **khác nhau** có trong dãy này.

#### Input

- Dòng đầu gồm 1 số nguyên $n$: số phần tử của dãy.
- Dòng thứ hai gồm $n$ số nguyên $x_1, x_2, ..., x_n$.

#### Output

- In một số nguyên: Số giá trị khác nhau.

#### Giới hạn
- $1 \le n \le 2\cdot10^5$
- $1 \le x_i \le 10^9$

#### Sample Input

5
2 3 2 2 3

#### Sample Output

2

#### Giải thích

- Có $2$ giá trị riêng biệt là $2$ và $3$.

#### Lời giải
- Đầu tiên, ta sẽ sắp xếp lại dãy trên theo thứ tự từ **bé đến lớn**.
- Sau khi dãy đã được sắp xếp, các phần tử có giá trị giống nhau sẽ đứng cạnh nhau, vì thế mỗi một **dãy liên tiếp** các phần tử có giá trị **bằng nhau**, ta chỉ đếm **một** lần.
- Duyệt dãy từ đầu đến cuối, ta sẽ đếm số vị trí $i$ sao cho $i \le n$ và $a_i \neq a_i-1$, để làm được điều này, ta sẽ dùng vòng lặp `while` để bỏ qua các phần tử đứng **cạnh nhau** nhưng có giá trị **bằng nhau**.
::: spoiler **Code mẫu**

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{    
    int n, ans = 0; //khai báo n và gán biến kết quả bằng 0
    cin >> n;
 
    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    sort(a + 1, a + n + 1); //sắp xếp theo thứ tự từ bé đến lớn
 
    a[0] = 0; //gán giá trị cho phần tử 0 để tránh sai sót khi xử lí i = 1
    for (int i = 1; i <= n; i++)
    {
        //nếu thỏa điều kiện 2 phần tử cạnh nhau có giá trị khác nhau
        //và i <= n ta sẽ cộng thêm 1 vào biến lưu kết quả
        while (a[i] == a[i - 1]) i++;
        if (i <= n) ans++;
    }
 
    cout << ans;
    return 0;
}

:::

# Bài 3: HSGTP9 - TP.HCM - 2022 - Làm việc nhà

- Trước hết, mong các bạn thông cảm vì tụi mình hiện không có link nộp bài dành cho bài tập này.

#### Đề Bài

- Bình hay giúp đỡ ba mẹ làm việc nhà. Để đảm bảo việc học, Bình chỉ có thể sắp xếp được một lượng thời gian $T$ để làm việc nhà. Bình lên danh sách những việc nhà mình có thể làm, đi kèm với thời gian cần đẻ thực hiện xong việc đó. Các việc nhà trên có thể thực hiện theo thứ tự bất kỳ, nhưng tại một thời điểm chỉ có thể thực hiện một việc nhất định. Bình đang tìm cách làm sao dể có thể thực hiện xong nhiều nhất các việc nhà trong danh sách của mình.
- **Yêu cầu:** Cho các việc nhà và thời gian cần để hoàn thành công việc đó. Bạn hãy viết chương trình cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian $T$.

#### Input

- Dòng đầu tiên chứa một số nguyên $T (0 \le T \le 10^9)$ là giới hạn thời gian.
- Dòng thứ hai chứa một số nguyên $C (0 \le C \le 100)$ là số lượng việc nhà.
- $C$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương cho biết thời gian cần để thực hiện xong một việc nhà trong danh sách. Giả sử thời gian tối đa để thực hiện một việc nhà là $10^9$.

#### Output

- Ghi ra một số nguyên cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian $T$.

#### Sample Input

6
3 
3 
6 
3

#### Sample Output

2

#### Giải thích

- Ta chọn được $2$ công việc là công việc thứ $1$ và công việc thứ $3$, tổng thời gian thực hiện là: $3+3=6\le T$.

#### Lời giải

- Trước hết, ta có một nhận xét như sau: Nếu Bình **có thể** chọn công việc tốn thời gian là $x$, **Bình** hoàn toàn có thể chọn những công việc tốn thời gian $\le x$. Nhưng chiều ngược lại **đôi khi không xảy ra** (khi thời gian công việc đúng bằng thời gian Bình có).
- Vì thế, khi ta chọn công việc, ta sẽ nghĩ đến những công việc tốn ít thời gian nhất để chọn ra đầu tiên.
- Từ đó, ta nhận thấy cách chọn tối ưu sẽ luôn là chọn $k$ phần tử nhỏ nhất, nhiệm vụ của ta là tìm ra số $k$ đó.
- Ta sắp xếp danh sách công việc theo thứ tự thời gian **không giảm**, sau đó lần lượt duyệt qua cả danh sách, nếu còn đủ thời gian để làm công việc thứ $i$, ta sẽ chọn công việc đó cho Bình thực hiện, nếu không thì in ra số công việc đã chọn.

::: spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

int housework[105];

int main()
{
    int t,c;
    cin >> t >> c;

    for(int i = 0; i < c; ++i) cin >> housework[i];

    int t1 = 0; // t1 là thời gian đã dùng để thực hiện công việc
    sort(housework, housework + c);
    for(int i = 0; i < c; ++i)
    {
        if(t1 + housework[i] > t)
        {
            cout << i;
            return 0;
        }
        else t1 += housework[i];
    }
    cout << c;
    return 0;
}

:::

# Bài 4: [Bedao Regular Contest 10 - Admissions](https://oj.vnoi.info/problem/bedao_r10_admissions)
#### Đề Bài

- Ở trường học Bedao nọ, hiệu trưởng **illya** có kế hoạch nâng cao thành tích môn Tin học của nhà trường nên đã quyết định mở lớp Chuyên tin dành cho những học sinh đạt kết quả cao trong kì thi đầu vào. Kì thi đầu vào ghi nhận có $N$ học sinh tham gia, học sinh thứ $i$ có số điểm môn Toán là $a_i$ và có số điểm môn Tin là $b_i$. Để đảm bảo lớp học chất lượng nhất có thể, hiệu trưởng **illya** đã các bước sàng lọc như sau:

- $A$ học sinh có số điểm Toán cao nhất sẽ được nhận vào lớp.
- Đối với các học sinh chưa được nhận vào lớp, thì $B$ học sinh có số điểm Tin cao nhất sẽ được nhận vào lớp.
- Đối với các học sinh chưa được nhận vào lớp, thì $C$ học sinh có tổng số điểm Toán và Tin cao nhất sẽ được nhận vào lớp.
- Đối với các học sinh chưa được nhận vào lớp lúc này sẽ không được nhận vào lớp nữa.
- Tuy vậy, hiệu trưởng **illya** lại rất đặc cách những bạn học sinh có số thứ tự nhỏ, cụ thể nếu hai học sinh có số điểm bằng nhau thì học sinh có số thứ tự nhỏ hơn sẽ được nhận. Là một nhân viên IT xuất sắc của nhà trường, bạn hãy giúp **illya** lập danh sách các học sinh được nhận vào lớp Chuyên tin nhé!

#### Input

- Dòng đầu tiên gồm $4$ số nguyên $N (N \le 1000)$, $A$, $B$, $C$ $(0 \le A, B, C \le N$ và $1 \le A + B + C \le N)$.
- Dòng thứ hai gồm $N$ số nguyên $a_1, a_2, ..., a_N$ lần lượt là số điểm toán của học sinh thứ $1, 2, ..., N$ $(0 \le a_i \le 100)$.
- Dòng thứ ba gồm $N$ số nguyên $b_1, b_2, ..., b_N$ lần lượt là số điểm Tin của học sinh thứ $1, 2, ..., N$ $(0 \le b_i \le 100)$.

#### Output

- Gồm danh sách các học sinh được nhận vào sắp xếp theo số thứ tự của các học sinh, mỗi dòng là một số thứ tự của một học sinh.

#### Sample Input

7 0 0 3
40 70 80 60 50 30 45
84 35 90 77 56 78 20

#### Sample Output

1
3
4

#### Giải thích

- Ở kì thi đầu vào lần này, ta sẽ lấy $C = 3$ người có tổng điểm môn Toán và Tin cao nhất, từ đó ta sẽ có danh sách tổng điểm như sau: $[124,105,170,137,106,108,65]$.
- Từ danh sách này ta sẽ chọn ra được $3$ tổng điểm cao nhất là $[124,170,137]$ tương ứng với học sinh thứ $1$, $3$, và $4$.

#### Lời giải

- Ta sẽ tạo struct cho mỗi học sinh để lưu những thông tin: điểm toán, điểm tin, điểm tổng và số thứ tự của từng bạn, lần lượt gọi là $toan$, $tin$, $tong$, $stt$. Thực hiện sắp xếp mảng 3 lần như sau:
- Lần đầu sắp xếp các phần tử theo $toan$ giảm dần, nếu 2 học sinh có $toan$ bằng nhau thì sắp xếp theo $stt$ tăng dần. Khi đó $A$ học sinh đầu tiên sẽ được nhận vào lớp, ta đánh dấu cho $A$ bạn này.
- Lần thứ hai sắp xếp các phần tử theo $tin$ giảm dần, nếu 2 học sinh có $tin$ bằng nhau thì sắp xếp theo $stt$ tăng dần. Tuy nhiên, ta sẽ loại các học sinh đã được đánh dấu ra sau cuối mảng. Khi đó $B$ học sinh đầu tiên sẽ được nhận vào lớp, ta tiếp tục đánh dấu cho $B$ bạn này (Vì $A + B + C \le N \Rightarrow B \le N - A - C < N - A + 1 \Rightarrow$ ta sẽ không gặp lại những bạn đã được nhận vào lớp từ lần đánh dấu đầu tiên).
- Lần thứ ba sắp xếp các phần tử theo $tong$ giảm dần, nếu 2 học sinh có $tong$ bằng nhau thì sắp xếp theo $stt$ tăng dần. Ta tiếp tục loại các học sinh đã được đánh dấu ra sau cuối mảng. Khi đó $C$ học sinh đầu tiên sẽ được nhận vào lớp, ta tiếp tục đánh dấu cho $C$ bạn này (Vì $A + B + C \le N \Rightarrow C < N - A - B + 1 \Rightarrow$ ta sẽ không gặp lại những bạn đã được nhận vào lớp từ 2 lần đánh dấu trước).
- Những bạn đã được đánh dấu là những học sinh được nhận vào lớp.

:::spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

bool ok[1001]; //ok[i] = true nếu bạn thứ i được nhận vào lớp

struct hocsinh
{
    int toan, tin, tong, stt; //struct lưu thông tin từng học sinh
};

bool compare1(hocsinh a, hocsinh b)
{
    //điểm toán 2 em học sinh khác nhau thì em có điểm cao hơn sẽ được ưu tiên hơn
    if (a.toan != b.toan) return a.toan > b.toan;
    //nếu không thì em có số thứ tự bé hơn sẽ được ưu tiên hơn
    return a.stt < b.stt;
}

bool compare2(hocsinh a, hocsinh b)
{
    //ưu tiên học sinh chưa được nhận vào lớp đứng trước học sinh đã được nhận
    if (ok[a.stt] != ok[b.stt]) return ok[a.stt] == false;
    if (a.tin != b.tin) return a.tin > b.tin;
    return a.stt < b.stt;
}

bool compare3(hocsinh a, hocsinh b)
{
    if (ok[a.stt] != ok[b.stt]) return ok[a.stt] == false;
    if (a.tong != b.tong) return a.tong > b.tong;
    return a.stt < b.stt;
}

int main()
{    
    int N, A, B, C;
    cin >> N >> A >> B >> C;

    hocsinh hs[N + 1];
    for (int i = 1; i <= N; i++)
    {
        cin >> hs[i].toan;
        hs[i].stt = i;
    }

    for (int i = 1; i <= N; i++)
    {
        cin >> hs[i].tin;
        hs[i].tong = hs[i].toan + hs[i].tin;
    }

    sort(hs + 1, hs + N + 1, compare1);
    for (int i = 1; i <= A; i++) ok[hs[i].stt] = 1;
    //nếu học sinh thứ i được nhận vào lớp thì ok[<số thứ tự em đó>] = 1 (true)

    sort(hs + 1, hs + N + 1, compare2);
    for (int i = 1; i <= B; i++) ok[hs[i].stt] = 1;

    sort(hs + 1, hs + N + 1, compare3);
    for (int i = 1; i <= C; i++) ok[hs[i].stt] = 1;

    for (int i = 1; i <= N; i++)
        if (ok[i] == true) cout << i << '\n';
        //nếu ok[i] = true nghĩa là học sinh thứ i đã được nhận
    return 0;
}

:::