【UVA-12100】Printer Queue【紫书】

【UVA-12100】Printer Queue【紫书】

问题链接:https://vjudge.net/problem/UVA-12100

Solution:

模拟,使用STL的队列,我们需要用一个数组来判断是否存在比当前优先级更高优先级的打印任务,由于优先级的范围是1到9,假设当前任务的优先级为p,那么判断是否可以打印这个任务实际上就是判断p+1开始的后缀和是否为0,如果是0就打印,我们设置一个偏移变量,叫做OFF,它的值设置成最大优先级+2就可以,接着将每个优先级p映射为下标OFF – p,这样我们把对后缀和的查询转化为了对前缀和的查询,可以使用树状数组来实现动态前缀和,对于每个任务,我们判断树状数组中OFF – p – 1前缀和是否为0.【注:正是因为这里要取OFF – p – 1,并且树状数组下标最小应当设置成1,那么我们应当保证\(OFF – p_{max} – 1 = 1\),求解可以确定\(OFF = p_{max} + 2\)】。接着,每次打印一个任务都将一个计数变量cnt自增一。而关于m,我们只要判断它是不是0,如果不是0,就说明当前任务不是要找的那个任务,直接判断它能否打印来控制,m固定会自减1,正常模拟就好;如果是0,则说明这个任务就是题目要找的任务,如果它还不能打印,则移到队尾时一定要把m设置为队列大小-1,如果可以打印就先自增cnt,之后输出答案,结束循环。

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int OFF = 11;
int bit[OFF], cnt;
queue<int> list;

inline void init() {
    memset(bit, 0, sizeof bit);
    cnt = 0;
    while (!list.empty()) list.pop();
}

inline int lowbit(int x) {return x & (-x);}

void update(int x, int diff) {
    while (x < OFF) {
        bit[x] += diff;
        x += lowbit(x);
    }
}

int query(int x) {
    int ret = 0;
    while (x > 0) {
        ret += bit[x];
        x -= lowbit(x);
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, t, tmp;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init();
        while (n--) {
            cin >> tmp;
            list.push(tmp);
            update(OFF - tmp, 1);
        }
        while (true) {
            tmp = list.front();
            list.pop();
            if (m) {
                if (query(OFF - tmp - 1)) list.push(tmp);
                else {
                    update(OFF - tmp, -1);
                    cnt++;
                }
                m--;
            } else {
                if (query(OFF - tmp - 1)) {
                    list.push(tmp);
                    m = list.size() - 1;
                } else {
                    cnt++;
                    cout << cnt << "\n";
                    break;
                }
            }
        }
    }
    return 0;
}