https://codeforces.com/contest/1810/problem/B
时间: 2023-10-01 10:11:01 浏览: 96
Solution:
We can solve this problem using binary search. Let's define a function `check(x)` which returns `True` if there exists a subarray of length `k` such that the difference between the maximum and minimum element of that subarray is less than or equal to `x`.
To implement this function, we can use two pointers. We start with two pointers `l=0` and `r=k-1`. We maintain the maximum and minimum element in the subarray `[l,r]` using two variables `mx` and `mn`. If `mx-mn<=x`, we return `True`. Otherwise, we move the left pointer to the right by incrementing `l` and update `mx` and `mn` accordingly. We keep moving the left pointer until `mx-mn<=x` holds. If we cannot find such a subarray, we return `False`.
Now, we can use binary search to find the minimum value of `x` such that `check(x)` returns `True`. We start with `l=0` and `r=10^9`. At each iteration, we compute the middle value `mid=(l+r)//2` and check if `check(mid)` returns `True`. If it does, we update `ans=mid` and set `r=mid-1`. Otherwise, we set `l=mid+1`. We continue until `l>r`.
Finally, we output the value of `ans`.
Time Complexity:
The function `check(x)` takes `O(n)` time to execute. The binary search algorithm takes `O(log_2(10^9))=30` iterations. Therefore, the overall time complexity of the algorithm is `O(n*log_2(10^9))`.
Space Complexity:
The algorithm uses `O(n)` space to store the input array.
Let's see the implementation:
阅读全文