GD5: Scheduling on many machines

main.cpp

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, m;
    scanf("%d %d", &n, &m);

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < m; i++) // init m machines
        pq.push(0);

    for (int i = 0; i < n; i++) { // process jobs
        int inp;
        scanf("%d", &inp);

        int cur = pq.top();
        pq.pop();
        pq.push(cur + inp);
    }

    int ans = 0;
    while (pq.size() > 0) {
        ans = max(ans, pq.top());
        pq.pop();
    }
    printf("%d\n", ans);
}

int main()
{
    int ncase;
    scanf("%d", &ncase);

    while (ncase--)
        solve();
    return 0;
}

main_my_pq.cpp

#include <bits/stdc++.h>

using namespace std;

// min heap
struct my_pq {
    int nxt = 0;
    vector<int> data;
    void clear()
    {
        data.clear();
        nxt = 0;
    }

    int top()
    {
        return data[0];
    }

    void pop()
    {
        if (nxt == 1)
            nxt = 0;
        else {
            data[0] = data[nxt - 1];
            nxt--;

            int cur = 0;
            while (cur < nxt) {
                /*
                    a
                   / \
                  b   c
                  a < b and a < c relation! Tricky to implement!
                */
                int change = cur;
                int l = lc(cur);
                if (l < nxt && data[l] < data[change])
                    change = l;
                int r = rc(cur);
                if (r < nxt && data[r] < data[change])
                    change = r;

                if (change != cur) {
                    swap(data[cur], data[change]);

                    if (change == l)
                        cur = l;
                    else
                        cur = r;
                } else
                    break;
            }
        }
    }

    int par(int x)
    {
        if (x % 2 == 0)
            return (x - 2) / 2;
        return (x - 1) / 2;
    }

    int lc(int x)
    {
        return x * 2 + 1;
    }

    int rc(int x)
    {
        return x * 2 + 2;
    }

    void push(int x)
    {
        if (nxt == (int)data.size())
            data.push_back(x);
        else
            data[nxt] = x;
        nxt++;

        int idx = (int)data.size() - 1;
        while (idx > 0) {
            int p = par(idx);
            if (data[p] > data[idx]) {
                swap(data[p], data[idx]);
                idx = p;
            } else
                break;
        }
    }

    int size()
    {
        return nxt;
    }
} pq;

void solve()
{
    int n, m;
    scanf("%d %d", &n, &m);

    pq.clear();
    for (int i = 0; i < m; i++) // init m machines
        pq.push(0);

    for (int i = 0; i < n; i++) { // process jobs
        int inp;
        scanf("%d", &inp);

        int cur = pq.top();
        pq.pop();
        pq.push(cur + inp);
    }

    int ans = 0;
    while (pq.size() > 0) {
        ans = max(ans, pq.top());
        pq.pop();
    }
    printf("%d\n", ans);
}

int main()
{
    int ncase;
    scanf("%d", &ncase);

    while (ncase--)
        solve();
    return 0;
}