โปรแกรม C++ หาช่วงเวลาน้อยที่สุดสูงสุดระหว่างคู่นาฬิกา

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

สมมติว่าเรามีอาร์เรย์ D N องค์ประกอบ ในงานเขียนโปรแกรมมีผู้เข้าร่วม N+1 คนรวมอมล อมลตรวจสอบว่าช่วงเวลาระหว่างเมืองของเขากับคนที่ i คือ D[i] ชั่วโมง ช่วงเวลาระหว่างเมือง A และ B: ถ้าเวลาท้องถิ่นเมือง B เป็น d โมง เมื่อเมือง A เป็น 0 โมง ช่วงเวลาคือ min(d, 24-d) ชั่วโมง ใช้ระบบ 24 ชั่วโมง สำหรับแต่ละคู่คนจาก N+1 คน เขาเขียนช่วงเวลาระหว่างเมืองของพวกเขา ให้ s เป็นช่วงเวลาน้อยที่สุดในคู่เหล่านั้น ต้องการหาค่า s สูงสุดที่เป็นไปได้

ตัวอย่าง: D = [7, 12, 8] ผลลัพธ์คือ 4 เพราะช่วงเวลาระหว่างคนที่ 2 และ 3 คือ 4 ชั่วโมง

ขั้นตอนการแก้ปัญหา

n := ขนาดของ D
เรียงลำดับ D
กำหนดอาร์เรย์ t
ใส่ 0 ลง t
สำหรับ i := 0 ถึง n-1:
    ถ้า i mod 2 == 0: ใส่ D[i] ลง t
    มิฉะนั้น: ใส่ 24 - D[i] ลง t
เรียงลำดับ t
ans := infinity
สำหรับ i := 1 ถึง ขนาด t - 1:
    ans := min(ans, t[i] - t[i-1])
คืนค่า ans

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

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

int solve(vector<int> D) {
    int n = D.size();
    sort(D.begin(), D.end());
    vector<int> t;
    t.push_back(0);
    for (int i = 0; i < n; i++){
        if (i % 2 == 0) t.push_back(D[i]);
        else t.push_back(24 - D[i]);
    }
    sort(t.begin(), t.end());
    int ans = 1e9;
    for (int i = 1; i < t.size(); i++){
        ans = min(ans, t[i] - t[i - 1]);
    }
    return ans;
}

int main(){
    vector<int> D = { 7, 12, 8 };
    cout << solve(D) << endl;
}

อินพุต

{ 7, 12, 8 }

เอาต์พุต

4