在不使用STL 容器的前提下实现下面这个代码#include <iostream> using namespace std; long long arr[900010]; long long SUM = 0; class heap{ private: long long *b; int s; public: heap(long long *P, int S):s(S){ b = new long long[900010]{0}; for(int i = 1; i <= s; ++i){ b[i] = P[i]; } for(int i = s / 2; i >= 1; --i) percolateDown(i); } ~heap(){ delete [] b; } void push(long long int X){ int T = ++s; for(; T > 1 && X < b[T / 2]; T /= 2) b[T] = b[T / 2]; b[T] = X; } void pop() { b[1] = b[s--]; percolateDown(1); } void percolateDown(int i){ if (i > s) return; int hole = i; long long T = b[i]; int child; for ( ; hole * 2 <= s ; hole = child) { child = hole * 2; if (child + 1 <= s && b[child] > b[child + 1]) ++child; if (T > b[child]) b[hole] = b[child]; else break; } b[hole] = T; } long long top() { return b[1];} bool empty() const { return s == 0; } }; int main(){ int N, M; cin >> N >> M; int k, num = 1; for(k = 1; k < 120; ++k){ num *= M; if (num >= N) break; } while(num > M + N - 2){ num -= M - 1; } for(int i = 1; i <= N; i++){ cin >> arr[i]; } heap Aheap(arr, num); while(1){ long long rt = 0; for(int i = 0; i < M; i++){ rt += Aheap.top(); Aheap.pop(); } SUM += rt; if(Aheap.empty()) break; else Aheap.push(rt); } cout << SUM; return 0; }

可以使用动态数组来替代数组，动态数组是在运行时动态分配内存的一种数组。具体实现方法如下：

class DynamicArray {
private:
    int* data;
    int capacity;
    int size;
public:
    DynamicArray(int initialCapacity) {
        capacity = initialCapacity;
        size = 0;
        data = new int[capacity];
    }

    ~DynamicArray() {
        delete[] data;
    }

    void push_back(int value) {
        if (size == capacity) {
            int* newData = new int[capacity * 2];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            delete[] data;
            data = newData;
            capacity *= 2;
        }
        data[size++] = value;
    }

    int& operator[](int index) {
        return data[index];
    }

    int size() {
        return size;
    }
};

在这里，我们使用了new运算符来动态分配内存，使用delete[]运算符来释放内存。在push_back()函数中，如果当前数组已经满了，就分配一个大小为原来两倍的新数组，然后将旧数组中的元素复制到新数组中，最后释放掉旧数组。在[]运算符重载函数中，我们返回对应索引的元素的引用，以便可以修改数组的值。在size()函数中，我们返回数组的大小。

在实际使用时，我们可以将DynamicArray作为heap类的私有成员，来实现动态数组的功能。