Link bài: Cách 1: Thuật toán: Sắp xếp các con búp bê lớn dần theo thứ tự kích thước. Ta dùng các con búp bê lớn nhất để chứa nhiều nhất các con búp bê nhỏ hơn. Ta có thể dùng thuật toán đệ quy để tính toán (Vì test bài này không quá lớn, nhưng sẽ không phải là cách tối ưu). Mỗi vòng đệ quy của búp bê kích thước Ai sẽ giúp tìm ra con búp bê thứ j (j < i) nhỏ hơn thỏa Aj + k < Ai. Vòng đệ quy con nhỏ hơn sẽ được gọi nhằm tính toán con búp bê nhỏ hơn Aj. Code: Mã: #include <bits/stdc++.h> using namespace std; long long int n, k, ans; int a[100007]; bool tp[100007]; void treat(int pos, int val){ for (int i = pos-1; i >= 1; i--) if (a <= val && tp) {treat(i, a-k); tp = 0; break;} } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("bube.inp", "r", stdin); //freopen("bune.out", "w", stdout); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a; sort(a+1, a+n+1); memset(tp, 1, sizeof(tp)); for (int i = n; i >= 1; i--) if (tp) {ans += a; treat(i, a-k);} cout << ans; return 0; } Cách 2: Thuật toán: Sắp xếp các con búp bê theo thứ tự. Duyệt theo thứ tự những con búp bê lớn trước. Ta sẽ dùng một priority queue để chứa các con búp bê, với những con búp bê tiếp theo bỏ vừa búp bê đầu priority queue, ta sẽ thế chỗ nó vào priority queue. Nếu không, ta sẽ chọn nó là búp bê nằm ngoài. Code: Mã: #include <bits/stdc++.h> #include <queue> using namespace std; int n, a[100007], k; long long int ans; priority_queue<int> q; void read(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("bube.inp", "r", stdin); //freopen("bube.out", "w", stdout); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a; } void run(){ sort(a+1, a+n+1); for (int i = n; i >= 1; i--){ if (q.size() == 0 || q.top() < a+k){ ans += a; q.push(a); } else{ q.pop(); q.push(a); } } cout << ans; } int main(){ read(); run(); return 0; }