Equator

Equator

Codeforces easy

يوجد مصفوفة \(A\) تحتوي على العدد \(N\) من الأعداد الصحيحة \(A_1, A_2, \dots, A_N\).
أوجد أول موقع \(i\) بحيث يكون المجموع \(A_1 + A_2 + ... + A_i\) على الأقل نصف مجموع المصفوفة الكاملة.

Noteملحوظة

المصفوفة \(A\) مرقمة بدءًا من \(1\) (أي أن الترقيم يبدأ من \(1\)).

Tipنصيحة

عند مقارنة عددين صحيحين، إذا كان أحدهما يتضمن قسمة، يمكنك تجنب القسمة بضرب الطرف الآخر بدلًا منها.

على سبيل المثال، بدلًا من كتابة:

if (running_sum >= total_sum / 2)

يمكنك أن تكتب:

if (running_sum * 2 >= total_sum)

هذا يتجنب مشاكل التقريب ويعمل بشكل صحيح مع الأعداد الصحيحة.

Solution

قم بحلقة تكرار على المصفوفة واحسب مجموعها الكامل ولنسمه total_sum.

int n;
cin >> n;

int a[n];
int total_sum = 0;

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

بعد ذلك، ابدأ حلقة أخرى ابتداءً من العنصر الأول مع إضافة قيمة كل عنصر إلى running_sum. عند إضافة كل عنصر، تحقق مما إذا كان running_sum قد وصل إلى نصف total_sum. الجواب سيكون أول موقع يحدث فيه هذا الأمر.

int running_sum = 0;
int ans;

for (int i = 0; i < n; i++) {
    running_sum += a[i];

    if (running_sum * 2 >= total_sum) {
        ans = i + 1;
        break;
    }
}

cout << ans;