Giải bài ntucoder TILE - Chồng gạch

Link bài:

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;
    sort(a+1, a+n+1, greater<int>());
    x = a[1];
    if (x == 0) cout << 1; else
    nang(2);
    
    return 0;
}