CTDL và giải thuật - Giải thuật tham lam
Anh Lộc làm nghề phụ hồ cho một công ty xây dựng, Anh nhận thấy rằng mỗi loại gạch đều có độ cứng khác nhau.
Giả sử rằng viên gạch có độ cứng k
chỉ có thể chịu được tối đa k
viên gạch khác chồng lên nó, nếu nhiều hơn thì nó sẽ bị vỡ.
Cho mảng a
gồm n
số nguyên dương lần lượt là độ cứng của các viên gạch.
Anh Lộc muốn lấy gạch và xếp chúng chồng lên nhau thành một chồng gạch cao nhất có thể mà không để vỡ viên gạch nào
Hãy tìm và in ra màn hình xem anh Lộc có thể xếp chồng gạch có độ cao lớn nhất là bao nhiêu.
Ví dụ:
- Test mẫu 1:
Input Output 5
1 1 2 1 13
Vớia = [1, 1, 2, 1, 1]
, thì kết quả sẽarrangeBricks(a) = 3
.
Ta cóa[0] = 1
nghĩa là nó có thể chịu được1
viên gạch xếp ở trên.a[1] = 1
nghĩa là nó có thể chịu được1
viên gạch xếp ở trên.a[2] = 2
nghĩa là nó có thể chịu được2
viên gạch xếp ở trên.a[3] = 1
nghĩa là nó có thể chịu được1
viên gạch xếp ở trên.a[4] = 1
nghĩa là nó có thể chịu được1
viên gạch xếp ở trên.
Vậy nên ta có thể xếp được chồng cao nhất gạch gồm 3
viên gạch với thứ tự lần lượt sẽ là: a[2] -> a[1] -> a[1]
.
Nghĩa là viên gạch có độ cứng 2
ở dưới cùng rồi đến 2
viên gạch có độ cứng 1
ở trên, chúng ta có thể tham khảo hình ví dụ ở bên dưới
Như hình thì ta không xếp thêm viên gạch nào lên chồng gạch này nữa, nếu xếp thêm 1
viên nữa thì tùy viên gạch trên cùng có độ cứng 1
không bị vỡ nhưng những viên gạch phía dưới có độ cứng 1
và 2
sẽ bị vỡ.
Hướng dẫn bài tập.
Với bài này áp dụng giải thuật tham làm là vô cùng hợp lý, viên gạch đặt vào đầu tiên của chồng gạch sẽ là viên gạch có độ cứng lớn hơn, các viên tiếp theo cũng ưu tiên những viên có độ cứng cao nhất có thể.
Để giải quyết bài này ta sẽ sắp xếp dãy a thành dãy giảm dần, và lần lượt sắp các viên có độ cứng cao nhất đến khi không còn sắp được nữa.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
#include<algorithm>
using namespace std;
void quickSort(int a[], int l, int r){
int p = a[(l+r)/2];
int i = l, j = r;
while (i < j){
while (a[i] < p){
i++;
}
while (a[j] > p){
j--;
}
if (i <= j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
if (i < r){
quickSort(a, i, r);
}
if (l < j){
quickSort(a, l, j);
}
}
int solve(int a[], int n){
int k = 1;
quickSort(a, 0, n-1);
int stiffness = a[n-1];
for (int i = n-2; i >=0; i--){
k = k + 1;
stiffness = stiffness - 1;
if (stiffness > a[i]){
stiffness = a[i];
}
if (stiffness == 0) return k;
}
return n;
}
int a[100001];
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
cout << solve(a, n);
return 0;
}