---
title
Tham lam - Bài tập và lời giải
---
Tham lam - Bài tập và lời giải
===
---
###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]
---
## Bài 1: [CSES - Towers](https://cses.fi/problemset/task/1073)
### Đề bài:
* Bạn được cấp $n$ khối theo một thứ tự nhất định và nhiệm vụ của bạn là xây dựng các tòa tháp bằng cách sử dụng chúng. Khi hai khối lập phương chồng lên nhau thì khối trên phải nhỏ hơn khối dưới.
* Bạn phải xử lý các hình khối theo thứ tự nhất định. Bạn luôn có thể đặt khối lập phương lên trên một tòa tháp hiện có hoặc bắt đầu một tòa tháp mới. Số lượng tháp tối thiểu có thể là bao nhiêu?
#### Input:
* Dòng đầu tiên gồm một số $n$: số khối. ($1 \le n \le 2 * 10^5$)
* Dòng tiếp theo gồm $n$ số là kích thước k của khối. ($1 \le k \le 10^9$)
#### Output:
* Ghi một số duy nhất là chi phí tối thiểu.
#### Sample Input:
```
5
3 8 2 1 5
```
#### Sample Output:
```
2
```
### Lời giải:
:::spoiler **Ý tưởng:**
* Với từng khối, ta sẽ xem xét đằng trước có khối nào lớn hơn để ta hợp cùng thành một tháp không:
_ Nếu có, ta sẽ dùng tìm kiếm nhị phân để tìm ra tòa tháp lớn hơn khối hiện tại nhưng nhỏ nhất trong các khối lớn hơn để tối ưu cách chọn, xong đó cập nhật lại độ lớn cho tháp hiện tại.
_ Nếu không, ta sẽ lưu lại khối này là một tòa tháp mới.
:::spoiler **Hint cài đặt:**
* Ta có thể dùng multiset để làm những thao tác trên.
:::
:::spoiler **Code mẫu:**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, a[200005];
multiset<int> s;
int main()
{
cin>>n;
for (int i = 0; i < n; i++){
cin>>a[i];
}
int ans=0;
for (int i = 0; i < n; i++){
auto p = s.upper_bound(a[i]);
if (p == s.end()){
ans++;
s.insert(a[i]);
}
else {
s.erase(p);
s.insert(a[i]);
}
}
cout << s.size();
return 0;
}
```
:::
## Bài 2: [Codeforces - The Party and Sweet](https://codeforces.com/problemset/problem/1158/A)
### Đề bài:
* Cho $n$ chàng trai và $m$ cô gái. Mỗi chàng trai quyết định tặng một số kẹo cho từng cô gái. Ta được cho mảng b gồm n phần tử với b[i] là số kẹo ít nhất mà chàng trai thứ i tặng cho 1 cô gái bất kì và mảng g gồm m phần tử với g[j] là số kẹo nhiều nhất mà cô gái thứ j nhận từ 1 chàng trai bất kì. Hãy tính tổng số kẹo ít nhất mà các chàng trai cần chuẩn bị để số kẹo thỏa các điều kiện của mảng b và g. Nếu không thể chuẩn bị kẹo theo yêu cầu thì đưa ra đáp án là $-1$.
#### Input:
* Dòng đầu tiên gồm hai số nguyên n và m - số lượng chàng trai và cô gái. ($2 \le n, m \le 10^5$)
* Dòng thứ hai là mảng b gồm n phần tử ($0 \le b[i] \le 10^8$)
* Dòng thứ ba là mảng g gồm m phần tử ($0 \le g[i] \le 10^8$)
#### Output:
* Ghi tổng số kẹo ít nhất mà các chàng trai cần chuẩn bị hoặc báo là không thực hiện được ghi ra -1.
#### Sample Input:
```
3 2
1 2 1
3 4
```
#### Sample Output:
```
12
```
* Giải thích: Tổng số kẹo tối thiểu mà các chàng trai có thể đưa ra là $12$. Khi đó, chàng trai đầu tiên sẽ tặng các cô gái $1$ và $4$ viên kẹo, chàng trai thứ hai tặng $3$ và $2$ viên kẹo và chàng trai thứ ba tặng $1$ và $1$ viên kẹo cho cô gái thứ nhất và thứ hai. Dễ dàng nhận thấy mọi điều kiện đều được thỏa mãn và tổng số kẹo là $12$.
### Lời giải:
:::spoiler **Ý tưởng:**
* Ta thấy rằng nếu số nhỏ nhất trong mảng $g$ bé hơn số lớn nhất trong $b$ thì trường hợp này không thực hiện được do luôn tồn tại số kẹo của một chàng trai lớn hơn số kẹo lớn nhất của một cô gái, vì thế điều kiện không thỏa mãn. Còn các trường hợp khác đều có đáp án.
* Để tối ưu số kẹo, ta thấy rằng ta nên chọn $b[j]$ lớn nhất trong tất cả $b[j]$ bé hơn $g[i]$, khi đó số kẹo chênh lệch của mỗi $b[j]$ và $g[i]$ là bé nhất làm cho số kẹo cần chuẩn bị thành nhỏ nhất.
:::
:::spoiler **Code mẫu:**
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
long long b[N], g[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> b[i];
for (int i = 1; i <= m; ++i)
cin >> g[i];
sort(b + 1, b + 1 + n, greater<>());
sort(g + 1,g + 1 + m);
int j = m;
long long sum = 0;
for (int i = 1; i <= n; ++i){
if (b[i] > g[1]){
cout << -1;
return 0;
}
long long add = m;
while (j >= 1 && b[i] < g[j] && add > 1){
sum += g[j];
--j;
--add;
}
while (j >= 1 && b[i] == g[j]){
sum += g[j];
--j;
--add;
}
sum += b[i] * add;
}
cout << sum;
return 0;
}
```
:::
## Bài 3: [CSES - Stick Divisions](https://cses.fi/problemset/task/1161)
### Đề bài:
* Bạn có một cây gậy có chiều dài $x$ và bạn muốn chia nó thành $n$ cây gậy có độ dài cho trước, có tổng chiều dài là $x$.
* Trong mỗi lần di chuyển, bạn có thể lấy bất kỳ cây gậy nào và chia nó thành hai cây gậy. Chi phí của hoạt động như vậy là chiều dài của thanh ban đầu.
* Chi phí tối thiểu cần thiết để tạo ra những chiếc gậy là bao nhiêu?
#### Input:
* Dòng đầu tiên gồm hai số nguyên $x$ và $n$: độ dài của cây gậy và số cây gậy được chia ra từ cây gậy ban đầu. ($1 \le n \le 2 * 10^5$) ($1 \le x \le 10^9$)
* Dòng thứ hai chứa $n$ số nguyên là độ dài của $n$ cây gậy được chia ra. (tổng độ dài của $n$ cây gậy này là $x$)
#### Output:
* Ghi một số duy nhất là chi phí tối thiểu cần thiết để tạo ra những chiếc gậy.
#### Sample Input:
```
8 3
2 3 3
```
#### Sample Output:
```
13
```
* Giải thích: Đầu tiên bạn chia que dài 8 thành que dài 3 và 5 (giá 8). Sau đó, bạn chia que có chiều dài 5 thành que có chiều dài 2 và 3 (giá 5). Tổng chi phí là 8 + 5 = 13.
### Lời giải:
:::spoiler **Ý tưởng:**
* Để ra được kết quả tối ưu nhất, ta phải gộp lại những thanh có độ dài nhỏ nhất hiện tại, rồi gộp lại dần cho tới khi chỉ còn một cây duy nhất. Nếu ta tách ra từ thanh ban đầu ra các thanh nhỏ hơn, chi phí sẽ bị dư thừa rất nhiều qua những lần tách.
:::
:::spoiler **Code mẫu:**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int x, n; priority_queue<int, vector<int>, greater<>> q;
int main()
{
cin >> x >> n;
for (int i = 1; i <= n; ++i){
int k;
cin >> k;
q.push(k);
}
long long ans=0;
for (int i = 1; i < n; ++i){
int a = q.top();
q.pop();
int b = q.top();
q.pop();
q.push(a + b);
ans += (a + b);
}
cout << ans;
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet