3633
60
Link bài:
Thuật toán:
VD: Viên gạch cứng nhất có độ cứng 50, nhưng viên gạch cứng thứ 2 có độ cứng 25 thì độ cứng của chồng 2 viên gạch trên là 25, tránh trường hợp chồng đủ 50 viên nhưng do vượt độ cứng của viên thứ 2 nên viên thứ 2 bị vỡ.
Code:
Thuật toán:
- Những viên gạch to hơn chắc chắn sẽ đặt được nhiều viên gạch hơn lên trên nó.
- Ta sắp xếp các viên gạch theo thứ tự tăng dần về độ cứng.
- Chọn lần lượt từng viên gạch kèm theo ràng buộc về độ cứng nhỏ nhất trong chồng gạch được chọn, tránh tình trạng quá tải.
VD: Viên gạch cứng nhất có độ cứng 50, nhưng viên gạch cứng thứ 2 có độ cứng 25 thì độ cứng của chồng 2 viên gạch trên là 25, tránh trường hợp chồng đủ 50 viên nhưng do vượt độ cứng của viên thứ 2 nên viên thứ 2 bị vỡ.
Code:
Mã:
#include <bits/stdc++.h>
using namespace std;
int a[107], n, ans, x;
void nang(int pos){
x--; ans++;
if (x < 0) cout << ans; else
if (a[pos] < x && a[pos] > 0) {x = a[pos]; nang(pos+1);} else
nang(pos+1);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("tile.inp", "r", stdin);
//freopen("tile.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a+1, a+n+1, greater<int>());
x = a[1];
if (x == 0) cout << 1; else
nang(2);
return 0;
}
