Оптимизировать код на C++

Question

Нужно добиться времени выполнения меньше секунды во всех случаях (при больших n). В данный момент программа работает чуть больше секунды, что неприемлемо. Подскажите, пожалуйста, что можно заменить и улучшить в алгоритме, чтобы он работал значительно быстрее. Задача:

Текущий код:

using namespace std;

int BorderSumLeft(int border, unsigned short *arr)
{
    int sumA = 0;
    int i = 0;
    while (i < border)
    {
        sumA += arr[i];
        ++i;
    }
    return sumA;
}

int BorderSumRight(int border, unsigned short *arr, int length)
{
    int sumB = 0;
    int i = border;
    while (i < length)
    {
        sumB += arr[i];
        ++i;
    }
    return sumB;
}

int main()
{
    int n;
    int border, result = -1;
    cin >> n;
    unsigned short *ticket = new unsigned short[n];
        for (int i = 0; i < n; i++)
        {
            cin >> ticket[i];
        }
        for (border = 1; border < n; border++)
        {
            if (BorderSumLeft(border, ticket) == BorderSumRight(border, ticket, n))
            {
                result = border;
                cout << border;
                break;
            }
        }
        delete[] ticket;
        if (result == -1)
        {
            cout << result;
        }
}

Answer 1

Как обычно - вы используете алгоритм O(N^2), в то время как надо один раз посчитать сумму, а потом поискать такое k, чтоб получить половину суммы...

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>

using namespace std;


int main()
{
    int n, sum = 0, k = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) { cin >> a[i]; sum += a[i]; } // Считаем сумму при чтении
    if (sum %2) { cout << -1 << endl; return 0; }  // Сумма нечетна - решения нет
    sum /=2;
    for(int s = 0; k < n; ++k)
    {
        s += a[k];
        if (s == sum) { cout << k+1 << endl; return 0; }  // Получили полсуммы
        if (s > sum) break;   // Превышено полсуммы - решения нет
    }
    cout << -1 << endl;
}

И еще - указывайте в будущем URL, а то приходится самому искать, что это https://www.e-olymp.com/ru/problems/2619

БЛОГ НА HUSL

Оптимизировать код на C++

Ответы (1 шт):