لو سمحت! كيفية حل MLE في الكود!

[ad_1]

وصلني هذا السؤال:

تتمتع أبقار المزارع جون بشغف كبير بالحلويات، وتستمتع بشكل خاص بتناول قصب الحلوى! لدى FJ إجمالي N من الأبقار، لكل منها ارتفاع أولي معين ويريد إطعامها M من قصب الحلوى، كل منها أيضًا بارتفاع متفاوت (1≥N، M≥2⋅10^5).
يخطط FJ لإطعام قصب الحلوى للأبقار واحدًا تلو الآخر، بالترتيب الوارد في الإدخال. لإطعام أبقاره قصب الحلوى، سيعلق قصب الحلوى بحيث يلامس قصب الحلوى الأرض في البداية. ستصطف الأبقار بعد ذلك واحدة تلو الأخرى، بالترتيب الذي قدمه الإدخال، وتصعد إلى قصب الحلوى، حيث تأكل كل منها ما يصل إلى ارتفاعها (نظرًا لأنها لا تستطيع الوصول إلى أي أعلى). تظل قصب الحلوى معلقة في مكانها حيث تم إعدادها في البداية ولا يتم إنزالها على الأرض، حتى بعد أن تأكل الأبقار الجزء السفلي من قصب الحلوى. من الممكن أن لا تأكل البقرة شيئًا أثناء دورها، إذا كانت قاعدة قصب الحلوى أعلى بالفعل من ارتفاع تلك البقرة. بعد أن تأخذ كل بقرة دورها، ينمو طول الأبقار بمقدار عدد وحدات قصب الحلوى التي تناولتها، ويقوم المزارع جون بتعليق قصب الحلوى التالي وتكرر الأبقار العملية مرة أخرى (حيث تكون البقرة 1 مرة أخرى أول من يبدأ في تناول قصب الحلوى) قصب الحلوى التالي). ملاحظة خاصة: قصب الحلوى يطفو في الهواء، على سبيل المثال عندما تصل بقرة يبلغ ارتفاعها 2 إلى قصب حلوى يبلغ ارتفاعه 3، فإنها تأكل الوحدتين (1 و 2)، والوحدة الثالثة من قصب الحلوى لا يزال يطفو في الهواء، لذلك يمكن فقط للأبقار التي يبلغ ارتفاعها ≥ 2 الوصول إليها وأكلها.

تنسيق الإدخال (الأنبوب القياسي):
السطر الأول يحتوي على N وM.
يحتوي السطر التالي على الارتفاعات الأولية لـ Ncows، كل منها في النطاق [1,10^9].
يحتوي السطر التالي على ارتفاعات قصب الحلوى M، كل منها في النطاق [1,10^9].

تنسيق الإخراج (الأنبوب القياسي):
الارتفاعات النهائية لكل من الأبقار N على خطوط منفصلة.
لاحظ أن الحجم الكبير للأعداد الصحيحة المتضمنة في هذه المشكلة قد يتطلب استخدام أنواع بيانات صحيحة 64 بت (على سبيل المثال، “طويلة طويلة” في C/C++).

إدخال العينة:
3 2
3 2 5
6 1
إخراج العينة:
7
2
7 الشرح:
يبلغ طول قصب الحلوى الأول 6 وحدات.
1. تأكل البقرة الأولى الجزء من قصب الحلوى الأول حتى ارتفاع 3، وبعد ذلك يحتل الجزء المتبقي من قصب الحلوى الأول ارتفاعات [3,6].
2. البقرة الثانية ليست طويلة بما يكفي لتأكل أيًا من الجزء المتبقي من قصب الحلوى الأول.
3. تأكل البقرة الثالثة وحدتين إضافيتين من قصب الحلوى الأول. الجزء المتبقي من قصب الحلوى الأول، يحتل المرتفعات [5,6]، لا يؤكل.
بعد ذلك، تنمو كل بقرة بمقدار الكمية التي أكلتها، وبذلك تصبح ارتفاعات الأبقار [3+3,2+0,5+2]=[6,2,7].
يبلغ طول قصب الحلوى الثاني وحدة واحدة، والبقرة الأولى تأكله كله.

التسجيل:

* المدخلات 2-10: N، M≤10^3
* المدخلات 11-14: لا توجد قيود إضافية.

وإليك إجابتي C ++:

سي ++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,m;
    cin>>n>>m;
    ll heightcow[n];
    for(int i=1;i<=n;i++){
        cin>>heightcow[i];
    }
    ll finalcow[n];
    for(ll i=1;i<=n;i++){
        finalcow[i]=heightcow[i];
    }
    ll heightcane[m];
    for(ll i=1;i<=m;i++){
        cin>>heightcane[i];
    }
    for(ll j=1;j<=m;j++){//cane
        bool statcane[m];
        for(ll i=1;i<=heightcane[j];i++){
            statcane[i]=true;
        }
        for(ll i=1;i<=n;i++){//cow
            for(ll k=1;k<=heightcow[i];k++){
                if(statcane[k]==true){
                    statcane[k]=false;
                    finalcow[i]++;
                }
            }
        }
    }
    for(ll i=1;i<=n;i++){
        cout<<finalcow[i]<<endl;
    }
    return 0;
}

ما حاولت:

ليس لدي أي فكرة عما يجب فعله، أنا مبتدئ. الرجاء المساعدة!

الحل 1

أول شيء تلاحظه بخصوص الكود هو أن الفهارس تمتد إلى ما بعد نهاية المصفوفات:

سي ++

ll heightcow[n] = { 3, 2, 5 };
ll heightcane[m] = { 6, 1 };
ll finalcow[n];

for (ll i = 1; i <= n; i++) { //<- error!!
    finalcow[i] = heightcow[i];
}

تبدأ المصفوفات دائمًا عند 0 وتنتهي عند n-1.

//يحرر:
ليس لدي أي تفسير لسبب طلب رمز MLE هنا. تتطلب المهمة رمزًا تسلسليًا بسيطًا لتغذية الأبقار يحسب حجم الأبقار بعد تناول قصب الحلوى:

سي ++

for (ll j = 0; j < m; j++) {
   ll lower_height = 0;
   ll upper_height = heightcane[j];

   for (ll i = 0; i < n && lower_height < upper_height; i++) {
       if (finalcow[i] >= lower_height) { 
         ll eaten = max((ll)0, min(finalcow[i], upper_height) - lower_height);
         finalcow[i] += eaten;
         lower_height += eaten; // new lower height 
       }
   }
}

[ad_2]