vanya-and-lanterns

Vanya and Lanterns

لديك خط طوله \(l\) وعليه \(n\) نقطة في المواقع \(a_1, a_2, \dots, a_n\). كل نقطة يمكنها “تغطية” مسافة \(d\) إلى اليسار و \(d\) إلى اليمين. ابحث عن أصغر \(d\) بحيث يتم تغطية كل نقطة على الخط من \(0\) إلى \(l\) بواسطة على الأقل واحدة من هذه النقاط.

ملحوظة

لطباعة متغير من نوع double باسم x بصيغة عشرية, يمكنك استخدام: cout << fixed << x;

Solution

أولاً، نقوم بترتيب النقاط من اليسار إلى اليمين بحيث يطابق ترتيبها في المصفوفة مواقعها على الخط.

لضمان تغطية الخط بالكامل، يجب أن تغطي كل نقطة على الأقل نصف المسافة إلى جارتها، والتي هي \((a_{i+1} - a_i)/2\) لكل \(1 \le i \le n - 1\).

النقطة الأولى \(a_1\) يجب أن تغطي أيضًا المسافة من بداية الخط (0) إلى نفسها، \(a_1 - 0\)، والنقطة الأخيرة \(a_n\) يجب أن تغطي المسافة من نفسها إلى نهاية الخط، \(l - a_n\).

أصغر \(d\) الذي يضمن تغطية الخط بالكامل هو أكبر هذه المسافات كلها.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, l;
    cin >> n >> l;

    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a, a + n);

    double d = max(a[0] - 0, l - a[n - 1]);

    for (int i = 0; i < n - 1; i++) {
        d = max(d, (a[i + 1] - a[i]) / 2.0);
    }

    cout << fixed << d << "\n";
}