## 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;
}
```
Do ta cần tách số nấm thành 2 phần liên tiếp sao cho tổng số nấm pha thuốc được là lớn nhất, ta dùng Kỹ Thuật 2 Con Trỏ kết hợp Prefix Sum để giải quyết bài toán, cụ thể:
- Gọi s[i][0] là số nấm nhiều nhất có thể đem đi pha thuốc từ [1, i].
- Gọi s[i][1] là số nấm nhiều nhất có thể đem đi pha thuốc từ [i, n].
Ta dễ dàng có thể chuẩn bị trước 2 mảng Prefix Sum dựa trên 2 con trỏ 2 đầu.
Dễ thấy kết quả chính là max (s[i][0] + s[i + 1][1]) với mọi i thuộc [1, n - 1].
Độ phức tạp: O(2n).
Code:
#include <bits/stdc++.h>
#define ll long long
#define FOR(i, a, b) for (ll i = (a); i <= (b); ++i)
#define FOD(i, a, b) for (ll i = (a); i >= (b); --i)
#define Mirai ios_base:: sync_with_stdio (0);
#define Kuriyama cin.tie (nullptr); cout.tie (nullptr);
using namespace std;
const ll maxN = 1e6 + 7;
template <class X, class Y> bool maximize (X &a, Y b) { if (a < b) return a = b, 1; return 0; }
// --------------- M1nK_08 --------------- //
ll n, k, x, r = 1, ans;
ll a[maxN], s[maxN][2];
void Solve () {
cin >> n >> k;
FOR (i, 1, n) cin >> a[i];
sort (a + 1, a + n + 1);
FOR (l, 1, n) {
while (r <= n && a[r] - a[l] <= k) {
s[r][0] = max (s[r - 1][0], r - l + 1);
r++;
}
}
r = n;
FOD (l, n, 1) {
while (r > 0 && a[l] - a[r] <= k) {
s[r][1] = max (s[r + 1][1], l - r + 1);
r--;
}
}
FOR (i, 2, n) maximize (ans, s[i - 1][0] + s[i][1]);
cout << ans;
}
signed main (void) {
Mirai Kuriyama;
Solve ();
return 0;
}
hungkm466
Created at
5 likes
M1nK_08
Created at
0 likes