rabbits-and-holes

الأرانب والجحور

الأولمبياد الوطني للبرمجة 2026 - المسابقة الرابعة، اليوم الأول

الزمن المحدد: 1 ثانية الذاكرة المحددة: 256 ميجابايت

يوجد \(N\) أرنبًا مصطفين على خط في الغابة، وقد رأوا أسدًا كبيرًا ويريدون الاختباء في جحورهم.

يوجد \(M\) جحرًا على الخط نفسه، ويمكن لكل جحر أن يستوعب أي عدد من الأرانب.

أُعطيت مواقع الأرانب الـ \(N\) ومواقع الجحور الـ \(M\) على الخط بالأمتار. يركض الأرنب بسرعة \(1\) متر في الثانية.

احسب أقصر زمن لازم لكي تختبئ جميع الأرانب في جحر.

المدخلات

يحتوي السطر الأول على عددين صحيحين \(N\) و \(M\).

يحتوي السطر الثاني على \(N\) عددًا صحيحًا: \(R_1, R_2, \dots, R_N\).

يحتوي السطر الثالث على \(M\) عددًا صحيحًا: \(H_1, H_2, \dots, H_M\).

المخرجات

اطبع عددًا صحيحًا واحدًا: أقصر زمن يمكن أن تختبئ خلاله جميع الأرانب.

التقييم

المهمة الفرعية	القيود	النقاط
\(1\)	\(N = 1,\ M = 1\)	\(5\)
\(2\)	\(N = 1\)	\(12\)
\(3\)	\(M = 1\)	\(13\)
\(4\)	جميع الأرانب تقع يسار جميع الجحور	\(15\)
\(5\)	\(N, M \le 1000\)	\(20\)
\(6\)	لا توجد قيود إضافية	\(35\)

القيود

\(1 \le N, M \le 10^5\)
\(1 \le R_i, H_i \le 10^9\)

أمثلة

المدخلات

4 5
30 60 10 20
25 80 50 10 70

المخرجات

الحل

سعة الجحور غير محدودة، لذلك يختار كل أرنب أقرب جحر مستقلًا. رتّب مواقع الجحور. لكل أرنب استخدم lower_bound وافحص أول جحر ليس إلى يساره وآخر جحر إلى يساره. الإجابة هي أكبر مسافة من هذه المسافات الدنيا. التعقيد \(O(M\log M+N\log M)\) زمنيًا و\(O(M)\) للذاكرة.

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

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

    vector<long long> rabbits(n), holes(m);
    for (long long& position : rabbits) cin >> position;
    for (long long& position : holes) cin >> position;

    sort(holes.begin(), holes.end());
    long long answer = 0;

    for (long long rabbit : rabbits) {
        auto it = lower_bound(holes.begin(), holes.end(), rabbit);
        long long nearest = (1LL << 60);

        if (it != holes.end()) {
            nearest = min(nearest, *it - rabbit);
        }
        if (it != holes.begin()) {
            nearest = min(nearest, rabbit - *prev(it));
        }

        answer = max(answer, nearest);
    }

    cout << answer << '\n';
}