ZeroJudge C421: Cloud Printing

A cloud printing service company has introduced a new type of service. The company operates N 3D printers, where printers P₁, P₂, …, P_k are designated to prioritize service for the most important customers, while printers P_k+1, P_k+2, …, P_N are slower and are intended to prioritize service for regular customers.

Each customer has a different printing priority based on the selected service level and the fees paid for the year. This priority is represented by 1 to 10,000, where 10,000 represents the highest printing priority and 1 represents the lowest.

To prevent customers with low printing priorities from waiting indefinitely, when any of the printers P₁ to Pₖ become available, the job with the highest priority among the waiting tasks is assigned to printing. Conversely, when any printers Pₖ₊₁ to Pₙ become available, the job with the lowest priority among the waiting tasks is assigned for printing.

Please write a program to list the order in which print jobs are assigned.

Sample Inputs/Outputs

Thought Process

Use a deque to store the data, but since the same numbers might be stored, an additional array should be created to record the count of each number’s occurrences. Since deleting data from the deque can be time-consuming, it’s important to minimize the number of deletions as much as possible.

When a number that is recorded in the array isn't already in the deque, it should be inserted into the deque. Use binary insertion to find the appropriate place for the insertion, which will save sorting time. If the received number is already present in the deque, simply increment the corresponding value in the array by 1.

When needing to delete data from the deque, first check if the value of the number in the array is 1. If it is, this means the number should be removed from the deque. If it is the first item to be deleted, use `pop_front()`. If it is the last item to be deleted, use `pop_back()`. If the value in the array is not 1, then no actual deletion is needed; simply decrement the array value by 1.

Sample Code－ZeroJudge C421: Cloud Printing

#include <iostream>
#include <deque>
using namespace std;

deque<int> vv;
int priority[50000] = {};

void bbinsert(const int target) {
    int left = 0, right = vv.size();
    while(left < right) {
        const int middle = (left + right)/2;
        if (vv[middle] < target) {
            left = middle+1;
        }
        else {
            right = middle;
        }
    }
    vv.emplace(vv.begin()+left, target);
}
int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, low = 0, high = 0, demand = 0;
    for (int i = 0; i<=10000; i++) priority[i] = 0;
    while (cin >> N && N != 0) {
        if (N == -1) {
            low++;
            if (demand > 0) {
                const int tmp = vv[0];
                cout << tmp << " ";
                if (priority[tmp] == 1) {
                    vv.pop_front();
                }
                priority[tmp]--;
                low--;
                demand--;
            }
        }
        else if (N == -2) {
            high++;
            if (demand > 0) {
                const int tmp = vv[vv.size()-1];
                cout << tmp << " ";
                if (priority[tmp] == 1) vv.pop_back();
                priority[tmp]--;
                high--;
                demand--;
            }
        }
        else {
            if (priority[N] == 0) bbinsert(N);
            priority[N]++;
            demand++;
        }
    }
    cout << "\n";
}

//ZeroJudge C421
//Dr. SeanXD