home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Smallest Range II ใน C++

คำอธิบายปัญหา

กำหนดอาร์เรย์ A และค่า K สำหรับแต่ละ A[i] เลือกบวก K หรือลบ K ได้เพียงครั้งเดียว ได้อาร์เรย์ B ต้องการให้ max(B) - min(B) น้อยที่สุด

ตัวอย่าง: A=[0,10], K=2 → B=[2,8] → diff=6

วิธีแก้ปัญหา (Sort + Greedy)

  1. เรียง A จากน้อยไปมาก
  2. คำตอบเริ่มต้น = A[n-1] - A[0] (ไม่บวกลบอะไร)
  3. พิจารณาแบ่งที่ i: ซ้ายบวก K, ขวาลบ K
  4. max = max(A[i]+K, A[n-1]-K)
  5. min = min(A[0]+K, A[i+1]-K)
  6. อัปเดตคำตอบ = min(คำตอบ, max-min)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int n = A.size();
        int ans = A[n-1] - A[0];
        
        for(int i = 0; i < n - 1; i++) {
            int mx = max(A[i] + K, A[n-1] - K);
            int mn = min(A[0] + K, A[i+1] - K);
            ans = min(ans, mx - mn);
        }
        return ans;
    }
};

int main() {
    vector<int> v = {0, 10};
    Solution ob;
    cout << ob.smallestRangeII(v, 2);
    return 0;
}

อินพุต

[0,10] 2

เอาต์พุต

6