C/C++教程

UVA - 210:Concurrency Simulator

本文主要是介绍UVA - 210:Concurrency Simulator,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目链接:https://vjudge.net/problem/UVA-210

题目分析

就是一道模拟题,但是细节有点多。
写代码两个小时,调试代码用了两天。。。很长时间不刷题了,这道虽然算法简单但是细节满满的题目对我来说是一个很好的热身。

  • 尽量不要去使用匿名名字空间,发现对调试过程不怎么友好(陈硕大大说的对)。
  • 使用枚举类型对程序的可读性、可维护性的提升非常大
  • 重载输入输出运算符的时候一定要记得返回stream对象
  • 这种带有switch语句的,可以使用Stragety模式,这里没有使用,因为每条语句只有执行,没有复杂的行为
  • 多组数据一定要有init函数清空数据
  • 使用智能指针不要用引用,这一点点内存的消耗不算什么,但是使用引用往往会带来错误:当我们在对象内部不小心将其释放掉的时候就会产生段错误,而且很难排查
  • 良好的抽象是巧妙设计的基础,每个类应该只负责其分内的事,不要尝试让其去做超过他权限的事,因为这样往往会让事情一团糟。封装、抽象能够帮助我们处理复杂的情况。
  • 通过ulimit -c unlimited命令开启生成core文件可以帮助进行调试
  • gdb调试开始的时候可以使用run < input.txt重定向输入和输出
  • cgdb真好用

AC代码

#include <iostream>
#include <array>
#include <vector>
#include <string>
#include <deque>
#include <memory>

using namespace std;

namespace {
enum TYPE {
    ASSIGN, PRINT, LOCK, UNLOCK, END
};
int n, quantum;

constexpr int MAXN = 26;
array<int, MAXN> alpha = {};

bool lock = false;
class Statement {
public:
    static constexpr int MAXN = 5;
    static array<int, MAXN> cost;
    static void init();
    string line;
    TYPE type;
    int var;
    int constant;
    int exec();
    friend istream& operator >> (istream& is, Statement &self);
    friend ostream& operator << (ostream& os, const Statement &self);
};

class Program {
public:
    vector<Statement> statements;
    int idx = 0;
    int id;
    bool exec();
    Program(int _id) : id(_id) {}

    friend istream& operator >> (istream& is, Program& self);
    friend ostream& operator << (ostream& os, const Program &self);
};
deque<shared_ptr<Program>> readyQueue, blockedQueue;
shared_ptr<Program> p;

ostream& operator << (ostream& os, const Statement &self) {
//    os << self.type;
    switch (self.type) {
        case ASSIGN:
            os << static_cast<char>('a' + self.var) << " = " << self.constant;
            break;
        case PRINT:
            os << "print " << static_cast<char>('a' + self.var);
            break;
        case LOCK:
            os << "lock";
            break;
        case UNLOCK:
            os << "unlock";
            break;
        case END:
            os << "end";
            break;
    }
    return os;
}

ostream& operator << (ostream& os, const Program &self) {
    os << "ID:" << self.id << "\n";
    for (auto s : self.statements) {
        os << s << "\n";
    }
    os << "\n";
    return os;
}

int Statement::exec() {
    switch (type) {
    case ASSIGN:
//        cout << "Test:" << line << endl;
//        cout << "Test:" << readyQueue.front()->id << " " << static_cast<char>('a' + var) << " = " << constant << endl;
        alpha[var] = constant;
        return cost[type];
        break;
    case PRINT:
        cout << p->id << ": " << alpha[var] << "\n";
        return cost[type];
        break;
    case END:
//        readyQueue.pop_front();
//        cout << "Test:" << type << " " << cost[type] << endl;
//        for (int i = 0; i < Statement::MAXN; ++i) {
//            cout << cost[i] << " ";
//        }
//        cout << endl;
        return cost[type];
        break;
    case LOCK:
        if (lock) {
            blockedQueue.push_back(p);
            return -1;
        } else {
            lock = true;
            return cost[type];
        }
        break;
    case UNLOCK:
        if (!blockedQueue.empty()) {
            readyQueue.push_front(blockedQueue.front());
            blockedQueue.pop_front();
        }
        lock = false;
        return cost[type];
    default:
        break;
    }
}

bool Program::exec() {
    int time = quantum;
    while (time > 0) {
        int ret = statements[idx].exec();
        if (ret == -1) {
            //lock
            return false;
        }
        if (++idx == statements.size()) {
            //end
            return false;
        }
        time -= ret;
    }
    return true;
}

constexpr int Statement::MAXN;
array<int, Statement::MAXN> Statement::cost;

void Statement::init() {
    for (int i = 0; i < MAXN; ++i) cin >> cost[i];
}

istream& operator >> (istream& is, Statement &self) {
    auto &line = self.line;
    getline(is, line);
    if (line[1] == ' ') {
        self.type = ASSIGN;
        self.var = line[0] - 'a';
        self.constant = stoi(line.substr(4));
    } else if (line[0] == 'p') {
        self.type = PRINT;
        self.var = line[6] - 'a';
    } else if (line[0] == 'l') {
        self.type = LOCK;
    } else if (line[0] == 'u') {
        self.type = UNLOCK;
    } else {
        self.type = END;
    }
    return is;
}
istream& operator >> (istream& is, Program& self) {
    auto &s = self.statements;
    do {
        s.push_back(Statement());
        is >> s.back();
    } while(s.back().type != END);
    return is;
}


}

void init() {
    readyQueue.clear();
    blockedQueue.clear();
    std::fill(alpha.begin(), alpha.end(), 0);
    lock = false;
}

int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);
    int T, id = 0;
    cin >> T;
    for (int caseIdx = 0; caseIdx < T; ++caseIdx) {
        if (caseIdx) cout << "\n";
        init();
        cin >> n;
        Statement::init();
        cin >> quantum;
        string line;
        getline(cin, line);
        for (int i = 0; i < n; ++i) {
            readyQueue.push_back(make_shared<Program>(i + 1));
            cin >> *readyQueue.back();
        }
//        for (auto p : readyQueue) {
//            cout << *p;
//        }
        while (!readyQueue.empty()) {
            //TODO:加上了&导致出错
            p = readyQueue.front();
            readyQueue.pop_front();
            if (p->exec()) {
                readyQueue.push_back(p);
            }
//            cout << "Test:[readyQueue]\n";
//            for (auto p : readyQueue) {
//                cout << *p;
//            }
//            cout << "Test:[blockedQueue]\n";
//            for (auto p : blockedQueue) {
//                cout << *p;
//            }
//            cout << flush;
        }
//        cout << "====================================\n";
    }
    return 0;
}

这篇关于UVA - 210:Concurrency Simulator的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!