算法习题---5-7打印队列（UVa12100）

一：题目

有一个打印机，有一些任务在排着队打印，每个任务都有优先级。
打印时，每次取出队列第一个任务，如果它的优先级不是当前队列中最高的，就会被放到队尾，否则就打印出来。
输出初始队列的第m个任务的打印时间，每次打印花费单位1的时间。

（一）样例输入

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

（二）样例输出

1
2
5

二：代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <deque>

using namespace std;

typedef struct
{
    int id;
    int priority;
}Elem;

deque<Elem> de_queue;　　//使用双端队列，其操作类似vector，但是可以两头操作

int main()
{
    freopen("data5_7_h.in", "r", stdin);
    freopen("data5_7_h.out", "w", stdout);

    int total, num, cur_id;
    Elem ele;
    cin >> total;
    for (int i = 0; i < total; i++)
    {
        de_queue.clear();
        cin >> num >> cur_id;    //信息获取
        for (int j = 0; j < num; j++)
        {
            ele.id = j;
            cin >> ele.priority;
            de_queue.push_back(ele);
        }
        //模拟操作
        int count = 0;
        while (true)
        {
            //先找到最高优先级
            int max_pri = 0;
            for (deque<Elem>::iterator it = de_queue.begin(); it != de_queue.end(); it++)
                max_pri > (*it).priority ? max_pri : max_pri = (*it).priority;
            //如果是出队该数据
            if (de_queue.front().id == cur_id&&de_queue.front().priority == max_pri)
            {
                count++;
                break;
            }
            else
            {
                if (de_queue.front().priority == max_pri)
                {
                    de_queue.pop_front();
                    count++;
                }
                else
                {
                    ele = de_queue.front();
                    de_queue.pop_front();
                    de_queue.push_back(ele);
                }
            }
        }
        cout << count << endl;
    }

    freopen("CON", "r", stdin);
    freopen("CON", "w", stdout);
    return 0;
}