الرغبات والاحتياجات

الرغبات والاحتياجات
الأولمبياد الوطني للبرمجة 2026 - المسابقة التجريبية

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

أنت في متجر تتصفح المنتجات. في قائمتك \(N\) عناصر مختلفة. تحتاج من العنصر رقم \(i\) إلى شراء \(A_i\) قطع، لكنك ترغب في شراء \(B_i\) قطع، حيث \(B_i \ge A_i\).

عندما تشتري قطعة تحتاج إليها تحصل على نقطة رضا واحدة، وعندما تشتري قطعة ترغب فيها تحصل على نقطتي رضا. مثلًا، إذا كان \(A_i=3\) و\(B_i=5\)، فكل واحدة من القطع الثلاث الأولى من النوع \(i\) تمنحك نقطة، والقطعتان الرابعة والخامسة تمنحك كل منهما نقطتين. أي قطعة بعد \(B_i\) لا تمنحك نقاطًا.

ما أقل عدد من القطع التي عليك شراؤها لتحصل على \(K\) نقاط رضا على الأقل؟ مضمون أنه يمكنك الحصول على \(K\) نقاط على الأقل.

المدخلات

يحتوي السطر الأول على \(N\) و\(K\)، حيث \(1 \le N,K \le 5000\). تحتوي الأسطر \(N\) التالية على \(A_i\) و\(B_i\)، حيث \(0 \le A_i \le B_i \le 10^6\).

المخرجات

اطبع أقل عدد من القطع اللازمة للحصول على \(K\) نقاط رضا على الأقل.

التقييم

المجموعة القيود النقاط
\(1\) \(B_i-A_i \ge K\) \(20\)
\(2\) \(A_1=A_2=\cdots=A_N\) \(20\)
\(3\) \(B_1=B_2=\cdots=B_N\) \(20\)
\(4\) \(K \le 100\) \(20\)
\(5\) لا توجد قيود إضافية \(20\)

مثال

المدخلات

3 5
3 4
2 3
2 4

المخرجات

4
الحل

تعطي أول \(A_i\) قطع من النوع \(i\) نقطة لكل قطعة، وشراءها كلها يفتح حتى \(C_i=B_i-A_i\) قطع تعطي نقطتين. استخدم برمجة ديناميكية لحقيبة الظهر؛ لتكن dp[c] أقل عدد من قطع النقطة الواحدة اللازمة لفتح ما لا يقل عن c من قطع النقطتين، مع حصر السعة عند \(K\). جرّب لكل حالة قابلة للوصول العدد المطلوب من قطع النقطتين، وأكمل أي نقاط باقية من قطع النقطة الواحدة غير المستخدمة. التعقيد \(O(NK)\) زمنيًا و\(O(K)\) للذاكرة.

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

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

    vector<int> a(n), bonus(n);
    long long totalBase = 0;

    for (int i = 0; i < n; i++) {
        int b;
        cin >> a[i] >> b;
        bonus[i] = min(k, b - a[i]);
        totalBase += a[i];
    }

    const long long INF = (1LL << 60);
    vector<long long> dp(k + 1, INF);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int c = k; c >= 0; c--) {
            if (dp[c] == INF) continue;
            int next = min(k, c + bonus[i]);
            dp[next] = min(dp[next], dp[c] + a[i]);
        }
    }

    long long answer = INF;

    for (int capacity = 0; capacity <= k; capacity++) {
        long long base = dp[capacity];
        if (base == INF) continue;

        long long use = 0;
        if (base < k) {
            use = min<long long>(capacity, (k - base + 1) / 2);
        }

        long long score = base + 2 * use;
        long long extraBase = max(0LL, k - score);

        if (extraBase <= totalBase - base) {
            answer = min(answer, base + use + extraBase);
        }
    }

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