Моя куча программа не работает с большими массивами - PullRequest
Новая
       56

Моя куча программа не работает с большими массивами

0 голосов
/ 14 октября 2019

Предположим, вы пытаетесь связать много книг вместе. Книги могут состоять из разного количества страниц. Например, книга A может содержать 12 страниц, а книга B - 500 страниц. Каждый раз, когда вы связываете две книги, общее усилие по переплету равно количеству страниц в обеих книгах. Например, Переплетная Книга A и Книга B потребуют 512 единиц усилий. Напишите программу, которая занимает одну строку ввода. Ваша программа должна выводить минимальные единицы усилия, необходимые для связывания всех книг.

Ввод: 100,12,6,40 Ввод: 234

Примечание: лучший способ связать эти книгиэто сначала связать 12 с 6, что стоит 18 единиц усилий. Теперь у нас есть книги размеров {100, 18, 40}. Затем мы можем связать 18 и 40, что стоит 58 единиц усилий. Теперь у нас есть книги размеров {100, 58}. И, наконец, мы связываем 100 и 58, что требует 158 единиц усилий. Таким образом, нам потребовалось 18 + 58 + 158 = 234 единицы усилий.

У меня есть рабочая программа, использующая кучу и приоритетную очередь, но эта программа не работает с большими массивами, такими как Input: 187,65,13,4,5,89,13,55,4,99,544. Правильный ответ 2480, но моя программа получает 2546. Вот как программа должна получить 2480:

Как получить 2480

Это мой код: 

int conStrToInt(string str) 
{
int res = 0;
for(int i = 0; i < str.length(); i++) {
    res = res * 10 + (str[i]-48);
}
return res;
 }

 int main() {
 string in;
 cin >> in;
 stringstream ss(in);
 string elem;

priority_queue<int, vector<int>, greater<int> > pq;
while(getline(ss, elem, ',')) {
    int temp = conStrToInt(elem);
    pq.push(temp);
}
long long res = 0;
long long a = pq.top();
pq.pop();

if(pq.empty()) {
    cout << 0 << endl;
    return 0;
}
int b = pq.top();
pq.pop();
while(!pq.empty()) {
    res += (a + b);
    a = a + b;
    b = pq.top();
    pq.pop();
}
res += (a+b);
cout << res << endl;
return 0;

}

1 Ответ

2 голосов
/ 14 октября 2019

Вот переписано main. Он выталкивает новый номер обратно в кучу. Если размер кучи уменьшается до 1 (т.е. куча пуста после одного щелчка), цикл останавливается. 

int main() {
    string in;
    cin >> in;
    stringstream ss(in);
    string elem;

    priority_queue<int, vector<int>, greater<int> > pq;
    while(getline(ss, elem, ',')) {
        int temp = conStrToInt(elem);
        pq.push(temp);
    }

    if(pq.empty()) {
        cout << 0 << endl;
        return 0;
    }

    long long res = 0;
    while (true) {
        long long a = pq.top();
        pq.pop();
        if (pq.empty()) {
            break;
        }
        long long b = pq.top();
        pq.pop();
        res += a + b;
        pq.push(a+b);
    }

    cout << res << endl;
    return 0;

}
...