### Hint:
* Ta cần ghép 2 phần tử nhỏ nhất và lớn nhất lại với nhau nếu tổng của chúng ≤ `k`.
* Nếu ghép được, ta loại bỏ cả 2.
* Nếu không ghép được, phần tử lớn nhất phải đứng riêng lẻ (loại bỏ `r`).
* Lặp quá trình này đến khi hết mảng.
Đây là kỹ thuật **two pointers** (hai con trỏ) sau khi đã **sắp xếp mảng**.
---
### Code tham khảo:
```cpp
#include <bits/stdc++.h>
#define ll long long
#define name "TASK"
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
using namespace std;
void solve(){
int n; ll k;
cin >> n >> k;
ll a[n];
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a+n);
int l = 0, r = n-1, res = 0;
while(l <= r){
if(l != r && a[l] + a[r] <= k) {
l++; r--; // ghép được
} else {
r--; // phần tử lớn nhất đứng một mình
}
res++;
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen(name".INP","r")) {
freopen(name ".INP","r",stdin);
freopen(name ".OUT","w",stdout);
}
solve();
cerr << '\n' << "Time collapsed: " << TIME << '\n';
return 0;
}
```
---
### Độ phức tạp
* Sắp xếp: `O(n log n)`
* Duyệt two pointers: `O(n)`
* Tổng: **`O(n log n)`**
---
### Kết luận
Bài toán sử dụng chiến lược **tham lam (greedy)** + **two pointers** sau khi sắp xếp để ghép tối ưu.
---
ducyn
Created at
0 likes