Join Us
Loading Similar Posts
Entering edit mode
Solution using DP
int split(vector<int> &v, int start, int end, int m, vector<vector<int>> &dp)
{
if ((end - start + 1) < m)
return INT_MIN;
if ((end - start + 1) < 2 * m)
return v[end] - v[start];
if (dp[start][end] != -1)
{
return dp[start][end];
}
int ans = INT_MAX;
for (int i = start + m - 1; i < end - m + 1; i++)
{
int l = split(v, start, i, m, dp);
int r = split(v, i + 1, end, m, dp);
if (l == INT_MIN || r == INT_MIN)
{
ans = max(ans, v[end] - v[start]);
}
else
{
ans = min(ans, max(l, r));
}
}
return dp[start][end] = ans;
}
int fun(vector<int> &nums, int m)
{
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
if (n < 2 * m)
{
return nums[nums.size() - 1] - nums[0];
}
int ans = INT_MAX;
for (int i = m - 1; i < n - m; i++)
{
int l = split(nums, 0, i, m, dp);
int r = split(nums, i + 1, n - 1, m, dp);
ans = min(ans, max(l, r));
}
return ans;
}
int main()
{
// vector<int> a = {5, 11, 13, 4, 12};
vector<int> a ={93, 32, 88, 9, 58, 15};
cout <<fun(a, 3);
}
Entering edit mode
Solution using Binary Search on Answers
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool check(vector<ll> &a, const ll &m, ll tar)
{
ll sz = 0, mn = a[0], mx = a[0];
for (ll i = 1; i < a.size(); i++)
{
mn = min(a[i], mn);
mx = max(a[i], mx);
sz++;
if (mx - mn > tar)
{
if (sz < m)
return false;
sz = 1;
mn = a[i];
mx = a[i];
}
}
if (mx - mn > tar || sz < m)
{
return false;
}
return true;
}
int main()
{
ll n, m;
cin >> n >> m;
vector<ll> a(n);
for (ll i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
int l = 0, r = a[n - 1];
while (l < r)
{
ll mid = l + (r - l) / 2;
if (check(a, m, mid))
r = mid;
else
l = mid + 1;
}
cout << l << endl;
}
