Разминка для мозгов: вроде простая задача...

Всем привет.
Имеется задача. На первый взгляд простая. Но моё решение валится на 5 тесте. Мой алгоритм прост:

• Сортируем камни по возврастанию
• Идём с конца и прибавляем вес текущего камня к переменной с минимальным значением( две переменные объявлены зарание и инициализированны 0 )
• В конце выводим модуль разницы этих двух переменных.

Вот реализация этого алгоритма:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int *w = new int[n];
    for ( int i = 0; i < n; i++ )
        cin >> w[i];

    sort( w, w + n );
    int w1, w2;
    w1 = w2 = 0;
    for ( int i = n - 1; i >= 0; i-- )
    {
        if( w1 > w2 )
            w2 += w[i];
        else w1 += w[i];
    }
    cout << abs( w1 - w2 ) << endl;
    return 0;
}

Результат уже известен. В чём ошибка алгоритма? И как бы вы решали эту задачу?

Возможно, какое-либо переполнение происходит на тесте 5. И выводится неверное значение.

Кроме того, минимальная разность чисел 1000 и 500 — -500. В условии не сказано, что разность должна быть положительной. Но этот вариант я проверил, оно вообще ни один тест не проходит.

Нет. Если заменить int везде( кроме типа main ) на long long, то ошибка остаётся.

Да, я пробовал. Включи фантазию. Попробуй придумать тест (ситуацию), когда твой алгоритм не сможет пройти тест.

Почитай Обсуждение на форуме. Там есть «непроходящие» наборы входных данных для разных тестов.

Например для набора

6
101 50 52 4 3 2

твоя программа выдаёт 2, а правильный результат 0.

Logika ,