Cho mảng A, mỗi A[i] cộng thêm K hoặc -K (mỗi phần tử chọn một lần). Tìm hiệu nhỏ nhất giữa max và min của mảng mới B.
Ví dụ: A=[0,10], K=2 → 6 (B=[2,8]).
Giải pháp:
Sort A
ret = A[n-1] - A[0] (không đổi)
right = A[n-1] - K, left = A[0] + K
For i=0..n-2:
mx = max(A[i]+K, right)
mn = min(A[i+1]-K, left)
ret = min(ret, mx - mn)Trả về ret
Ý tưởng: sau khi sort, tồn tại điểm cắt i mà A[0..i] +K, A[i+1..n-1] -K cho kết quả tối ưu.
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int smallestRangeII(vector<int>& A, int k) { int n = A.size(); sort(A.begin(), A.end()); int ret = A[n-1] - A[0]; int right = A[n-1] - k, left = A[0] + k; for(int i = 0; i < n-1; i++){ int mx = max(A[i] + k, right); int mn = min(A[i+1] - k, left); ret = min(ret, mx - mn); } return ret; } }; int main(){ vector<int> v={0,10}; Solution ob; cout << ob.smallestRangeII(v, 2); }Đầu vào
[0,10] 2
Đầu ra
6