【UVA-12412】A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

【UVA-12412】A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

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

Solution:

这个题。。。有一种《C Primer Plus》或《C++ Primer Plus》课后作业的感觉。难度不大,题目要求查询的时候按照原顺序输出,同时注意到学生数最多100个,预估没有使用其它更快查找方法的必要,每次直接\(O(n)\)遍历查询。

建议在编码前设计好各个模块,采用模块化的思路,减少模块间的耦合度,这样可以减少人为出错的几率,同时也对排查错误很有帮助。

然后这道题比较有价值的是:

1)我下面的代码使用了链表的数据结构,使用数组来实现,让0号结点的下一个结点将是链表的开头,同时规定最后一个结点的下一个结点是0号结点,使用一个变量【我把它叫做last】表示尾结点在数组中的位置,使用另外一个变量【我叫做pos】表示目前最大使用到的数组位置,如果移除某个结点后,就把那个结点的位置加到一个vector或者queue里,表示数组中前面有位置已经失效,可以被新的数据覆盖了,每次插入结点先判断vector或queue里是否存放有已经失效的结点位置,如果有就优先放到数组中那个位置,如果没有则放在pos处,并将pos增加。这样链表实现方法在实际项目中不建议使用,由于是竞赛题目,为了减少不必要的申请内存时间消耗,可以这样实现。

2)这道题在精度上有坑点,数据会有浮点误差,将那几个浮点数加上一个精度值【经测设1e-4、 1e-5、 1e-6都是可行的】后就可以通过了。

3)Fast I/O,对于这道问题并不需要的,从最后结果来看,它的数据很水,0ms跑完,在有些竞赛程序中十分重要,特别是题目明确说明输入会很大的时候,这个时候可以通过:

ios::sync_with_stdio(false);

cin.tie(NULL);

来提速,但是需要注意,上面那行将使C++提供的iostream解除与C的stdio的同步,默认是true,设为false后就不要使用scanf和printf了;而cin.tie(NULL)则是将cin和cout解绑,这个绑定原本的作用是保证在cin尝试读取输入时刷新输出流【这个操作会产生一些耗时】,在交互式程序中十分必要,在竞赛程序中不需要,因为输入都是预先设定好的。【需要注意的是,如果手动在控制台中调试的时候要把这个注释掉,否则可能会出现输入输出顺序混乱的问题】

还有一种更快的Fast I/O方法,常常是大量输入的情况下,手动通过getchar()来实现一个输入函数读取整数、浮点数,如这道题目:https://www.spoj.com/problems/INTEST/

 

C++实现:

#include <iostream>
#include <queue>
#include <string>
#include <set>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

const int LIM = 120;
const int SIZE = 4;
const int CLASSCNT = 20 + 1;
const double EPS = 1e-6;
struct Student {
    string sid, name;
    int cid;
    int score[SIZE];
    int rank, tot;
    int nxt, pre;
};
struct Rank {
    int idx, score;
    bool operator < (const Rank & r) const { return score > r.score; }
};
Student list[LIM];
Rank val[LIM];
queue<int> emptyIdx;
set<string> exists;
vector<Student> ret;
enum {CH, MATH, EN, PRO, ALL};
int pos = 1, last = 0, rankLen, passedCnt[CLASSCNT][SIZE], overCnt[CLASSCNT][SIZE + 1], num[CLASSCNT] = {0}, sum[CLASSCNT][SIZE];
bool newestRank = false;

bool isSid(const string &str) {
    return isdigit(str[0]);
}

bool add(const Student & stu) {
    if (exists.find(stu.sid) != exists.end()) return false;
    newestRank = false;
    int p;
    if (!emptyIdx.empty()) {
        p = emptyIdx.front();
        emptyIdx.pop();
    } else {
        p = pos++;
    }
    list[p] = stu;
    for (int i = 0; i < SIZE; i++) list[p].tot += list[p].score[i];
    list[last].nxt = p;
    list[p].pre = last;
    list[p].nxt = 0;
    last = p;
    exists.insert(stu.sid);
    num[list[p].cid]++, num[0]++;
    return true;
}

int del(const string &str) {
    newestRank = false;
    int cnt = 0, p;
    if (isSid(str)) {
        for (p = list[0].nxt; p; p = list[p].nxt)
            if (list[p].sid == str) {
                list[list[p].pre].nxt = list[p].nxt;
                list[list[p].nxt].pre = list[p].pre;
                if (p == last) last = list[p].pre;
                emptyIdx.push(p);
                exists.erase(list[p].sid);
                num[list[p].cid]--, num[0]--;
                return 1;
            }
    } else {
        last = 0;
        for (p = list[0].nxt; p; p = list[p].nxt)
            if (list[p].name == str) {
                list[list[p].pre].nxt = list[p].nxt;
                list[list[p].nxt].pre = list[p].pre;
                emptyIdx.push(p);
                exists.erase(list[p].sid);
                num[list[p].cid]--, num[0]--;
                cnt++;
            } else {
                last = p;
            }
    }
    return cnt;
}

void calRank(void) {
    if (!newestRank) {
        int rank = 1;
        memset(passedCnt, 0, sizeof passedCnt);
        memset(overCnt, 0, sizeof overCnt);
        memset(sum, 0, sizeof sum);
        rankLen = 0;
        for (int p = list[0].nxt; p; p = list[p].nxt, rankLen++) {
            val[rankLen].score = 0;
            val[rankLen].idx = p;
            int tmp = SIZE;
            for (int i = 0; i < SIZE; i++) {
                val[rankLen].score += list[p].score[i];
                if (list[p].score[i] >= 60) passedCnt[0][i]++, passedCnt[list[p].cid][i]++;
                else tmp--;
                sum[0][i] += list[p].score[i];
                sum[list[p].cid][i] += list[p].score[i];
            }
            overCnt[0][tmp]++, overCnt[list[p].cid][tmp]++;
        }
        sort(val, val + rankLen);
        for (int i = 0; i < rankLen; i++) {
            if (i && val[i].score != val[i - 1].score) rank = i + 1;
            list[val[i].idx].rank = rank;
        }
        newestRank = true;
    }
}

void query(const string &str) {
    if (!newestRank) calRank();
    int p;
    ret.clear();
    if (isSid(str)) {
        for (p = list[0].nxt; p; p = list[p].nxt) {
            if (list[p].sid == str) {
                ret.push_back(list[p]);
                return;
            }
        }
    } else {
        for (p = list[0].nxt; p; p = list[p].nxt)
            if (list[p].name == str) ret.push_back(list[p]);
    }
}

inline void statics(void) {
    if (!newestRank) calRank();
}

inline void showMenu() {
    cout << "Welcome to Student Performance Management System (SPMS).\n\n"
        << "1 - Add\n"
        << "2 - Remove\n"
        << "3 - Query\n"
        << "4 - Show ranking\n"
        << "5 - Show Statistics\n"
        << "0 - Exit\n\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.setf(ios::fixed);
    cout.precision(2);
    int op = 0;
    Student tmp;
    string str;
    tmp.tot = 0;
    showMenu();
    while (cin >> op && op) {
        if (op == 1) {
            while (true) {
                cout << "Please enter the SID, CID, name and four scores. Enter 0 to finish.\n";
                cin >> tmp.sid;
                if (tmp.sid == "0") break;
                cin >> tmp.cid >> tmp.name;
                for (int i = 0; i < SIZE; i++) cin >> tmp.score[i];
                if (!add(tmp)) cout << "Duplicated SID.\n";
            }
        } else if (op == 2) {
            while (true) {
                cout << "Please enter SID or name. Enter 0 to finish.\n";
                cin >> str;
                if (str == "0") break;
                int cnt = del(str);
                cout << cnt << " student(s) removed.\n";
            }
        } else if (op == 3) {
            while (true) {
                cout << "Please enter SID or name. Enter 0 to finish.\n";
                cin >> str;
                if (str == "0") break;
                query(str);
                for (int i = 0; i < ret.size(); i++) {
                    cout << ret[i].rank << " "
                        << ret[i].sid << " "
                        << ret[i].cid << " "
                        << ret[i].name;
                    for (int j = 0; j < SIZE; j++) cout << " " << ret[i].score[j];
                    cout << " " << ret[i].tot
                        << " " << 1.0 * ret[i].tot / SIZE + EPS << "\n";
                }
            }
        } else if (op == 4) {
            cout << "Showing the ranklist hurts students' self-esteem. Don't do that.\n";
        } else if (op == 5) {
            cout << "Please enter class ID, 0 for the whole statistics.\n";
            statics();
            cin >> op;
            cout << "Chinese\n"
                << "Average Score: " << 1.0 * sum[op][CH] / num[op] + EPS << "\n"
                << "Number of passed students: " << passedCnt[op][CH] << "\n"
                << "Number of failed students: " << num[op] - passedCnt[op][CH] << "\n\n"
                << "Mathematics" << "\n"
                << "Average Score: " << 1.0 * sum[op][MATH] / num[op] + EPS << "\n"
                << "Number of passed students: " << passedCnt[op][MATH] << "\n"
                << "Number of failed students: " << num[op] - passedCnt[op][MATH] << "\n\n"
                << "English\n"
                << "Average Score: " << 1.0 * sum[op][EN] / num[op] + EPS << "\n"
                << "Number of passed students: " << passedCnt[op][EN] << "\n"
                << "Number of failed students: " << num[op] - passedCnt[op][EN] << "\n\n"
                << "Programming\n"
                << "Average Score: " << 1.0 * sum[op][PRO] / num[op] + EPS << "\n"
                << "Number of passed students: " << passedCnt[op][PRO] << "\n"
                << "Number of failed students: " << num[op] - passedCnt[op][PRO] << "\n\n"
                << "Overall:\n"
                << "Number of students who passed all subjects: " << overCnt[op][4] << "\n"
                << "Number of students who passed 3 or more subjects: " << overCnt[op][3] + overCnt[op][4] << "\n"
                << "Number of students who passed 2 or more subjects: " << overCnt[op][2] + overCnt[op][3] + overCnt[op][4] << "\n"
                << "Number of students who passed 1 or more subjects: " << overCnt[op][1] + overCnt[op][2] + overCnt[op][3] + overCnt[op][4] << "\n"
                << "Number of students who failed all subjects: " << overCnt[op][0] << "\n\n";
        }
        showMenu();
    }
}