Получение WA в УВА 10954

Question

Давайте добавим немного изобретательности к нему. Операция сложения требует затрат сейчас, а стоимость является суммой этих двух, которые будут добавлены. Итак, чтобы добавить 1 и 10, вам нужна стоимость 11. Если вы хотите добавить 1, 2 и 3. Есть несколько способов 1 + 2 = 3, стоимость = 31 + 3 = 4, стоимость = 42 + 3 = 5, стоимость = 53 + 3 = 6, стоимость = 62 + 4 = 6, стоимость = 61 + 5 = 6, стоимость = 6 Всего = 9 Всего = 10 Всего = 11 Я надеюсь, что вы уже поняли свою миссию, чтобы добавить набор целых чисел так, чтобы стоимость минимальна. Входные данные Каждый тестовый пример начинается с положительного числа N(2N5000), за которым следуют N положительных целых чисел (все меньше 100000). Ввод прекращается в случае, когда значение N равно нулю. Этот случай не должен обрабатываться. Выходные данные Для каждого случая выведите минимальную общую стоимость сложения в одной строке.

Пример ввода

3   
1 2 3   
4  
1 2 3 4  
0  

Пример вывода

9  
19  

я попытался отсортировать указанный массив, а затем взял другой массив для cumsum (CS) и суммировал все элементы CS, кроме cs[0].. я получаю WA для этого подхода, пожалуйста, объясните

int n,i,hold=0;   

while(1)   
{
    cin>>n;

    if(n==0){break;}

    int arr[n],cs[n];

    for(i=0;i<n;i++) cin>>arr[i];

    sort(arr,arr+i);

    cs[0]=arr[0];

    for(i=1;i<n;i++){cs[i]=arr[i]+cs[i-1]; }

    cs[0]=0;
    int sum=0;
    for(i=1;i<n;i++){sum+=cs[i]; }
    cout<<sum<<endl;
    sum=0;

}

вход:

9
66 85 52 22 44 1 59 88 67 
0

мой выход:

1822

ожидаемый результат (удебуг):

1454

получать WA

Answer 1

Используйте минимальную кучу и добавьте 2 самых маленьких элемента. Пример:

1 2 3 -> 3 3 -> 6. 1 2 3 4 -> 3 3 4 -> 4 6 -> 10.

Надеюсь, это поможет.

Answer 2

Ваша идея неверна, чтобы решить эту проблему. после взятия всех элементов в структуре данных вы должны повторить следующие 3 пункта: 1) сортировать. 2) суммируйте первые два значения и удалите первые два значения из структуры данных. 3) добавьте сумму к стоимости и структуре данных.
Вы можете использовать priority_queue в качестве структуры данных.