[数据结构与算法]uva210 循环链表+队列+索引=＞模拟

uva210

• 程序循环进行 ： 循环链表
• Lock未遂的程序依次抓走 ： 队列
• 数据结构刚好看到循环链表，感觉写好了插入删除很方便

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <string>
#include <cstring>

using namespace std;
struct Node;

#define TEST 1

typedef Node *pNode;
typedef queue<string> Program;

struct Node
{
    Node(int k, pNode p = NULL) : n(k), next(p) {}
    int n;
    pNode next;
};

//创建n个节点，第 i 个的值是 i - 1， 返回头节点地址
pNode Create(int n)
{
    pNode ret = new Node(-1);
    pNode cur = ret;
    for (int i = 0; i != n; ++i)
    {
        cur->next = new Node(i);
        cur = cur->next;
    }
    cur->next = ret;
    return ret;
}

//删除d节点，返回d节点前边的节点，这个在后边很有用
pNode del(pNode h, pNode d)
{
    while (h->next != d)
        h = h->next;
    h->next = d->next;
    delete d;
    return h;
}

//在队列中取出一个放到curr后边
void toback2(pNode curr, queue<int> &iq)
{
    curr->next = new Node(iq.front(), curr->next);
    iq.pop();
}

void run(ostream &);

int Q;                          //每个程序运行最大时长
int Time[5];                    //5个命令各自用时
int v[26];                      //26个变量
int pro_cnt;                    //程序数
bool LOCK;                      //是否Locking
vector<Program> Kase;           //每一个Program对应一个程序，每执行一行对应pop一行

int main()
{
    ofstream ofs;

    if (TEST)
    {
        ofs.open("/home/lixiaoqi/Documents/Code/C++/1.txt");
        if (!ofs.is_open())
            throw runtime_error("FILE NOT OPEN!");
    }
    ostream &os = TEST ? ofs : cout;

    int N;
    string s;

    cin >> N;
    getchar();
    while (N--)
    {
        Kase.clear();
        LOCK = false;
        memset(v, 0, sizeof v);

        cin >> pro_cnt;
        for (int i = 0; i != 5; ++i)
            cin >> Time[i];
        cin >> Q;

        Kase.resize(pro_cnt);

        getchar();
        for (int i = 0; i != pro_cnt; ++i)
            while (getline(cin, s) && s != "end")
                Kase[i].push(s);

        run(os);
        os << (N ? "\n" : "");
    }

    return 0;
}

void run(ostream &os)
{
    queue<int> block;                           //LOCK未遂的那些
    pNode h = Create(pro_cnt);
    pNode cur = h;

    /*每一个程序执行完，都要在循环链表中走一步，遇见头节点再走一步
     *在程序执行时，用left代表剩余时间控制循环，同时还要注意对应这个程序是否已经finish
     *程序全部执行完，要即时在链表中删除
     */
    while (h->next != h)
    {
        if (cur == h)
            cur = cur->next;
        int left = Q;
        int i = cur->n;

        while (Kase[i].size() && left > 0)
        {
            string s = Kase[i].front();

            if (s == "lock")
            {
                if (!LOCK)
                {
                    left -= Time[2];
                    LOCK = true;
                }
                else
                {
                    block.push(i);
                    cur = del(h, cur);
                    break;
                }
            }
            else if (s == "unlock")
            {
                if (block.size())
                    toback2(cur, block);
                LOCK = false;
                left -= Time[3];
            }
            else if (s[0] == 'p' && s[1] == 'r')
            {
                os << i + 1 << ": " << v[s[6] - 'a'] << '\n';
                left -= Time[1];
            }
            else
            {
                int k = 0;
                for (int j = 4; j != s.size(); ++j)
                    k = k * 10 + s[j] - '0';
                v[s[0] - 'a'] = k;
                left -= Time[0];
            }

            Kase[i].pop();
        }

        if (Kase[i].empty())
            cur = del(h, cur);

        cur = cur->next;
    }
}