## Hướng dẫn:
Vì Marisa cần làm 2 lọ thuốc cho nên ta cần chọn ra 2 tập phần tử có tổng số phần tử là nhiều nhất thoả mãn điều kiện bài toán.
Cách làm tương tự như bài [Pha thuốc 2](https://marisaoj.com/problem/508).\
**Lưu ý:** 2 tập phần tử được chọn có thể **liên tiếp** hoặc **không liên tiếp**.\
Bài này ta nên kết hợp giữa kĩ thuật **Hai con trỏ** và **Mảng tiền tố/ hậu tố**.\
Cụ thể:
- pre[i] là số lượng phần tử lớn nhất của 1 tập con thoả mãn trong [1, i]
- suf[i] là số lượng phần tử lớn nhất của 1 tập con thoả mãn trong [i, n]
➙ ANS = max(pre[i] + suf[i]) (1 ≤ i ≤ n)\
Code:
```
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=a; i<=b; ++i)
#define FORD(i,a,b) for (int i=a; i>=b; --i)
template<class X, class Y>
bool maximize(X &x, const Y &y) { return (x < y) ? x = y, 1 : 0; }
const int MAXN = 1e5 + 5;
int n, k;
int a[MAXN];
int pre[MAXN], suf[MAXN];
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
FOR(i,1,n) cin >> a[i];
sort(a+1,a+n+1);
int l = 1;
FOR(r,1,n)
{
while (l<=r && a[r] - a[l] > k) ++l;
maximize(pre[r], pre[r-1]);
maximize(pre[r], r-l+1);
}
int r = n;
FORD(l,n,1)
{
while (l <= r && a[r] - a[l] > k) --r;
maximize(suf[l], suf[l+1]);
maximize(suf[l], r-l+1);
}
int ans = 0;
FOR(i,1,n)
{
maximize(ans, pre[i] + suf[i+1]);
maximize(ans, pre[i-1] + suf[i]);
}
cout << ans;
return 0;
}
```
hungkm466
Created at
0 likes